binarySearch

Use binarySearch to find an element in sorted or monotonic space.

#include <iostream>
#include <vector>

using namespace std;

int binarySearch(vector<int> &arr, int x){
    int start = 0;
    int end = (int)arr.size() - 1;
    while (start <= end){
        int mid = start + (end - start) / 2;
        if (arr[mid] == x) return mid; // if found, return that index
        if (arr[mid] < x) start = mid + 1; // if x is greater than the middle one, ignore left half
        else end = mid - 1; // if x is smaller than the middle one, ignore right half
    }

    return -1; // if we couldn't find the element, return -1 or any failure sign code
}

Both average and worst case has O(log N) time complexity.