Binary Search

Binary search is an efficient algorithm to find a particular element in a sequence. It works in logarithmic time as it follows the divide and conquer strategy and decreases the search space by half in each iteration.

If the elements in the given sequence can be converted into the sequence of some 0s (falsy) followed by 1s (truthy) by using a predicate function f on each element of the sequence, then we can apply binary search to find the first 1 (truthy) or the last 0 (falsy) value.

Note that a predicate function always outputs true or false.

For the sequence 00...11..., the code for finding the index of the last 0 and the first 1 is:

int l = 0, r = n - 1, last_0, first_1;
while (l <= r) {
  int mid = l + (r - l) / 2;
  // the sequence is given in vector v, and f is the predicate function
  if (f(v[mid])) {
    r = mid - 1;
    first_1 = mid;
  } else {
    l = mid + 1;
    last_0 = mid;
  }
}

I will recommend you to memorize a template for binary search (the above can be used) and should not waste your brain's processing power every time in determining whether to use < or ≤ in the while loop or how to set l and r.

Binary search is a powerful tool for a programmer, which is often used. It is always recommended to beginners on codeforces who can't climb the competitive programming ladders. The theory is easy; however, the problem is it's not easy to determine the predicate function for the given sequence or even know if binary search can be applied. This all comes with practice.

We will go through some classical binary search problems.

Search in Rotated Sorted Array#

Problem: There is an integer array nums sorted in ascending order (with distinct values). After a possible rotation and given an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

Code:

bool f(const vector<int>& nums, int mid, int target) {
  if (nums[mid] < nums.back()) {
    return (target > nums.back()) || (target < nums[mid]);
  } else {
    return (target > nums.back()) && (target < nums[mid]);
  }
}

int search(vector<int>& nums, int target) {
  int n = nums.size();
  int l = 0, r = n - 1, res = -1;
  while (l <= r) {
    int mid = l + (r - l) / 2;
    if (nums[mid] == target) {
      res = mid;
      break;
    }
    if (f(nums, mid, target)) {
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  return res;
}