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)

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;
}

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

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