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

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.

Sample Implementation: (3 conditions)

Untitled

Lower/Upper Bound Problems

<aside> 💡 When you are said to find minimum/maximum based upon a given condition, you might need to use binary search.

</aside>

Here, you might need to merge the == condition with < or > , where you need to save it in a temporary variable as possible answer.

<aside> 💡 you can create a f(x) that will return T or F.

</aside>

Untitled

Let’s talk about the 2nd one. It’s Also known as lower or upper bound.