#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>

// Hàm tìm kiếm tuyến tính
int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; ++i) {
        if (arr[i] == key) {
            return i; // Trả về chỉ số của phần tử nếu tìm thấy
        }
    }
    return -1; // Trả về -1 nếu không tìm thấy
}

// Hàm tìm kiếm nhị phân
int binarySearch(int arr[], int n, int key) {
    int left = 0;
    int right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == key) {
            return mid; // Trả về chỉ số của phần tử nếu tìm thấy
        }
        if (arr[mid] < key) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // Trả về -1 nếu không tìm thấy
}

int main() {
    // Khởi tạo bộ sinh số ngẫu nhiên
    srand(time(0));

    // Tạo mảng ngẫu nhiên có ít nhất 1000 số nguyên
    const int N = 1000;
    int M[N];
    for (int i = 0; i < N; ++i) {
        M[i] = rand(); // Tạo số ngẫu nhiên
    }

    // Chọn ngẫu nhiên một giá trị K từ mảng M
    int K = M[rand() % N];

    // Thực hiện tìm kiếm tuyến tính
    clock_t startTime = clock();
    int linearResult = linearSearch(M, N, K);
    clock_t linearEndTime = clock();
    double linearTime = double(linearEndTime - startTime) / CLOCKS_PER_SEC;

    // Thực hiện tìm kiếm nhị phân (yêu cầu mảng M được sắp xếp trước)
    std::sort(M, M + N);
    startTime = clock();
    int binaryResult = binarySearch(M, N, K);
    clock_t binaryEndTime = clock();
    double binaryTime = double(binaryEndTime - startTime) / CLOCKS_PER_SEC;

    // In kết quả và thời gian thực hiện
    std::cout << "Linear search result: " << linearResult << " Time: " << linearTime << " seconds" << std::endl;
    std::cout << "Binary search result: " << binaryResult << " Time: " << binaryTime << " seconds" << std::endl;

    return 0;
}