Binary Search

Binary search is a search algorithm used to search in sorted input. Its essense it we choose a point in middle of the input and compare the target. Since the input is sorted ascendingly, if the target is greater than the middle element, then our target can be found in right part and if the target is smaller than the middle value, then our target can be found in the left part. Therefore using this approach we have divided our input to half.Now we continue doing the division and searching the middle element until out target is found or our input is exhausted.

Since we are dividing our search space by half on each iteration, the time complexity of this algorithm is O(logn).

Since we dont use any extra memory other than the given input and the element, the space complexity of this algorithm is O(1).

Code

bool binary_search(vector<int> &vec, int target) {
  int low = 0;
  int high = vec.size() - 1;
  while(low <= high) {
    int mid = low + (high - low) / 2;
    if(vec[mid] == target) {
      return true;
    } else if(vec[mid] > target) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return false;
}