Binary Search

I always get confused with the bounds.

Resources

• Binary Search tutorial (C++ and Python)
  • Biggest learning here is that binary search also works on an array that looks like [true, true, true, false, false, false]!
• Competitive Programmer’s Handbook

Code that I use for Competitive Programming:

int l = 0;
int r = arr.size() - 1;
while (l <= r) {
    int mid = (l+r)/2;
    if (arr[mid] == val) {
        return mid;
    } else if (arr[mid] < val) {
        l = mid + 1;
    } else {
        r = mid-1;
    }
}

Does binary search work if there are duplicate values??

Yes, as long as the function you’re searching over is Monotonic Function. (ACTUALLY, it depends on the problem). Look at the example application below, we can’t have duplicate values.

You can also use the built in library in C++, since it is faster. But I also encourage you when needed to write it yourself.

/*PAY ATTENTION HERE: 
- For lower bound, If it finds the first element equal to "val". If not found, it points to the first element greater than "val".
- However, for upper bound, it finds the first value greater than "val"
 
In general, always use lower_bound()
*/
auto lower = std::lower_bound(a.begin(), a.end(), val)

• https://cplusplus.com/reference/algorithm/lower_bound/ Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val.
• https://cplusplus.com/reference/algorithm/upper_bound/ returns an iterator pointing to the first element in the range [first,last) which compares greater than val.

Finding first number smaller than “val”?

set<int> a;
set<int>::iterator it = a.lower_bound(5);
if (it != a.begin()) {
  it--;
  cout << *it << endl;
} else {
  cout << "No smaller element found!" << endl;
}

For a decreasing array, you can feed in a custom operator:

auto itr3 = lower_bound(vec.begin(),vec.end(),40,std::greater<int>());

• Source: https://stackoverflow.com/questions/67705226/lower-and-upper-bound-in-case-of-decreasing-non-ascending-vector

Applications

You can boil down a lot of search problems that don’t seem like search problems at first, but they are.

Ex: Finding the smallest solution

Related

Actually, the idea of splitting the problem in half really comes more more often than I thought. It allows us to go from $O(n)$ to $O(\log n)$ for lots of problems. These are some of the ideas:

• Lowest Common Ancestor (Binary Lifting)
• Successor Graph → computing $succ(x,k)$
• Tree Query → finding the ancestor
• Fenwick Tree and
• Segment Tree
• Binary Exponentiation