Binary search cheatsheet

binary-search.md

Binary Search Cheatsheet

1. Find an exact target in sorted array

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

2. Find first number not smaller than (>=) target

int find(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 // nums[mid] > target
            right = mid;
    }
    return right;
}

Noted that no need to check nums[mid] == target. An alternative in C++ STL lower_bound:

std::vector<int>::iterator low;
low = std::lower_bound (v.begin(), v.end(), 20); 

Transformation: find last number smaller then target.

 return right - 1;

3. Find first number larger than (>) target

int find(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 // nums[mid] > target
            right = mid;
    }
    return right;
}

Similarly, a transformation is to find last number not larger than (<=) target.

  return right - 1;

For this transformation, C++ STL upper_bound:

std::vector<int>::iterator low,up;
low= std::lower_bound (v.begin(), v.end(), 20); 
up = std::upper_bound (v.begin(), v.end(), 20);

Difference

References

LeetCode Binary Search Summary