Binary Search is a search algorithm that finds the position of a target value within a sorted array. Example :We use Binary search while searching a word in dictionary

Calculation of Middle :

mid =(low+high)/2 might cause integer overflow in some problems .
So we use a different way to avoid it. For odd length there is only one mid , but for even length input space we must choose one mid.

1. StepDown/Floor : int mid=low+(high-low)/2 Favors left one in even length
2. StepUp/Ceil : int mid= low+ (high-low+1)/2 Favors right one in even length

Note high-low can also cause integer overflow if high is INT_MAX and low is INT MIN but that will rarely happen as we will deal with mainly indexes or positive values .So my tip would be to be aware of the Constraints of the problem.

1. Basic

https://leetcode.com/problems/binary-search/
https://leetcode.com/problems/search-insert-position
https://leetcode.com/problems/sqrtx
https://leetcode.com/problems/first-bad-version/
https://leetcode.com/problems/valid-perfect-square/
https://leetcode.com/problems/guess-number-higher-or-lower/
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array M

2. Rotated Sorted arrays

https://leetcode.com/problems/search-in-rotated-sorted-array/
https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

3. Binary Search on Answer 💎💎💎

Hardest part of these type of problems is to figure out whether binary search can be used or not.
Once you know binary search is applicable these problems become very easy.

Search space looks like this
❌❌❌❌❌❌✅✅✅✅✅✅✅✅✅
where
❌ means condition fails
✅ means condition passes

875. Koko Eating Bananas
https://leetcode.com/problems/maximum-candies-allocated-to-k-children/
https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/
https://leetcode.com/problems/split-array-largest-sum/ H
https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/
https://leetcode.com/problems/divide-chocolate/ [Locked] CN
1870. Minimum Speed to Arrive on Time
https://leetcode.com/problems/minimum-time-to-complete-trips/ ✏️
https://leetcode.com/problems/minimize-maximum-of-array/ ✏️
https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/ ✏️
https://leetcode.com/problems/find-the-safest-path-in-a-grid/ BFS+ BS on Answer

4. Matrix

https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/ PQ is a better alternative
https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/
https://leetcode.com/problems/search-a-2d-matrix/ M
https://leetcode.com/problems/search-a-2d-matrix-ii/
https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/ ✏️

5. LIS variants

https://leetcode.com/problems/longest-increasing-subsequence/
https://leetcode.com/problems/russian-doll-envelopes/ ✏️

6. Multiple arrays

https://leetcode.com/problems/minimum-common-value/
https://leetcode.com/problems/median-of-two-sorted-arrays/

7. Math/count

https://leetcode.com/problems/arranging-coins/
https://leetcode.com/problems/find-the-duplicate-number/ Binary search on count (Overkill)

8. Tree

https://leetcode.com/problems/count-complete-tree-nodes/
https://leetcode.com/problems/closest-nodes-queries-in-a-binary-search-tree/

C++ STL syntax

/* Vector must be sorted in increasing order for binary search */
lower_bound( v.begin(), v.end(), ele ); /* Lower Bound : Returns iterator to first element >=ele */
upper_bound( v.begin(), v.end(), ele ); /* Upper Bound : Returns iterator to first element >ele */
binary_search( v.begin(), v.end(), ele ); /* binary_search : Return true if element 'ele' is found */