BinarySearch

BinarySearch.cpp

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

class BinarySearch {
private:
    vector<int> data;   // Sorted array
    int comparisons;    // Count of comparisons

    int searchRecursive(int left, int right, int x) {
        if (left <= right) {
            int mid = left + (right - left) / 2;
            comparisons++;  // One comparison

            if (data[mid] == x) return mid;

            if (x < data[mid])
                return searchRecursive(left, mid - 1, x);
            else
                return searchRecursive(mid + 1, right, x);
        }
        return -1;
    }

public:

    BinarySearch(const vector<int>& arr) : data(arr), comparisons(0) {}

    int search(int x) {
        comparisons = 0;
        return searchRecursive(0, data.size() - 1, x);
    }

    int getComparisons() const { return comparisons; }
};

int main() {
    const int N = 1000;
    vector<int> arr(N);
    srand(time(0));

    for (int i = 0; i < N; ++i)
        arr[i] = i * 2;

    for (int i = 0; i < arr.size(); ++i) {
        cout << arr[i] << " ";
    }

    BinarySearch bs(arr);

    int x;
    cout << "Enter a number to search: ";
    cin >> x;

    int index = bs.search(x);

    if (index != -1)
        cout << "Element found at index: " << index << endl;
    else
        cout << "Element not found." << endl;

    cout << "Comparisons made: " << bs.getComparisons() << endl;
    return 0;
}