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.
Simple binary search algo. Remember a few things:
General Implementation: (3 conditions)
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.
Try to stick to the general implementation structure shown above.
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.