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, it points to that element, but if not, it points to the closest element above.
- However, for upper bound, it ALWAYS points to the next closest element
 
In general, always use lower_bound()
*/
auto lower = std::lower_bound(a.begin(), a.end(), val)

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