Binary Search

Binary search may be one of the most intuitive algorithms: when the search space is sorted, then we can make a guess first (usually the middle in the range of [left, right)) to see whether the "guessed" value fits the condition or not. Based on the result with the "guessed" value, we can adjust the search range by removing either the first half or the second half.

Some key points:

1. The search space may be an abstract one. The basic understanding is that: if the "middle" value is Okay, and all the values smaller (or larger) than it are also Okay, then we can consider to use binary search;

2. In some special cases, binary search is NOT always the most efficient method for sorted data (for example, two sum problem with a sorted array);

3. The boundary conditions are tricky to handle.

The template of the lower_bound index (the index of the first element equal to the target if exists; or the index of the first element (maybe the end of the array) larger than the target if not)

class Solution {
public:
    int lower_bound(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        return left;
    }
};

The template of the upper_bound index: (the index of the first element (maybe the end of the array) larger than the target)

class Solution {
public:
    int upper_bound(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] <= target) left = mid + 1;
            else right = mid;
        }
        return left;
    }
};

Notes:

1. the only difference is: one is < and the other is <=;

2. if the target does not exist in the array, they are the same.