References:

https://www.youtube.com/watch?v=GU7DpgHINWQ

https://usaco.guide/silver/binary-search?lang=cpp

As you know, everything has its good, better and the best.

General Implementation

Simple binary search algo. Remember a few things:

  1. while (l≤r) . NOT while (l<r)
  2. mid = l + (r-l)/2 . NOT mid = (l+r)/2 as it might create overflow.
  3. Ensure not overflowed.
  4. Also note the L and R updating.

General Implementation: (3 conditions)

Untitled

The binary search maintains the following invariant: • All indices less than left are false. • All indices greater than or equal to left might be true.

First True/False Problems

Try to stick to the general implementation structure shown above.

image.png

The idea behind the binary search for the first "true" is that when you find a mid that evaluates to true, you don't immediately conclude that mid is the answer. Instead, you try to see if there's an even smaller index that also yields true by moving the right pointer. Let me explain with an invariant and an example.