# Binary Search

## Summary table

algorithm | bisect_left | bisect_right |
---|---|---|

lo | 0 | 0 |

hi | len(arr) | len(arr) |

criterion | arr[mid] >= t | arr[mid] > t |

bisection | arr[mid:] >= t | arr[mid:] > t |

FFFFTTTT | arr[mid] -> arr[mid] is first T | |

TTTTFFFF | not arr[mid] -> arr[mid-1] is last T |

## Remarks

- The binary search algorithm solves the problem of finding a target within a sorted sequence.
- The algorithm works by iteratively updating the lower or upper bound of the search space where the target if exist should reside.
- The update is done by checking the middle element of search space. Comparing it with the target and figure out which half of the search space it should it be.
- The algorithm runs in O(logN) time worst case, because we are iteratively cutting the search space in half.
- Prefer left inclusive right exclusive pattern for bisect_left and right. But ok with exact find with both end inclusive.

## Advanced Usages

- We can apply binary search on the domain of a monotonic function.
- The given sequence as a whole may not be ordered, but if we know certain subsequence is ordered, we can apply binary search on the subsequence.
- [In longest increasing / non-decreasing sub-sequence problem, binary search can be used with a stack to speed up the DP tabulation.][1]

## Examples Code

- To find a value in array:

```
# both inclusive version
def binary_search(arr, t):
lo, hi = 0, len(arr) - 1 # search space [0, n - 1]
while lo <= hi: # both inclusive thus need = sign here
mid = (hi + lo) >> 1
if arr[mid] == t: return mid
if arr[mid] > t: hi = mid - 1 # new search space [lo, mid - 1]
else: lo = mid + 1 # new search space [mid + 1, hi]
return -1
# left inclusive, right exclusive
def binary_search(arr, t):
lo, hi = 0, len(arr) # search space [0, n)
while lo < hi: # right is exclusive thus no need for = sign here
mid = (hi + lo) >> 1
if arr[mid] == t: return mid
if arr[mid] > t: hi = mid # new search space [lo, mid)
else: lo = mid + 1 # new search space [mid + 1, hi)
return -1
```

In case the target value occurs more than once, this binary search code will find one, but not guarantee to be either leftmost or rightmost.

- bisect left

```
def binary_search_left(arr, t):
lo, hi = 0, len(arr)
while lo < hi:
mid = (hi + lo) // 2
if arr[mid] >= t: hi = mid # new search space [lo, mid)
else: lo = mid + 1 # new search space [mid + 1, hi)
return lo
```

returns `i`

, such that `arr[:i] < t`

and `arr[i:] >= t`

.

Watch out the condition, if `arr[mid] == t`

we still set `hi = mid`

, which means, mid will be excluded from our search space, but our loop will only terminate if `lo == hi`

, meaning we are not totally excluding this `mid`

from be finally returned. When we search the `[lo, mid)`

space without success, we eventually will return this `mid`

value.

- bisect right

```
def binary_search_right(arr, t):
lo, hi = 0, len(arr)
while lo < hi:
mid = (hi + lo) // 2
if arr[mid] > t: hi = mid # new search space [lo, mid)
else: lo = mid + 1 # new search space [mid + 1, hi)
return lo
```

returns `i`

, such that `arr[:i] <= t`

and `arr[i:] > t`

, also the first i such that the criterion is True.

Example bisect left and bisect right on an arrary, and what happens when it go out of range.

```
arr = [1,2,3,3,5]
for t in range(7): print(binary_search_left(arr, t), binary_search_right(arr, t))
```

```
0 0
0 1
1 2
2 4
4 4
4 5
5 5
```

**if replace t < arr[mid] with f(mid): -> Bool**

- apply to range(boolean) of function over search space

```
def binary_search_left(arr, func):
lo, hi = 0, len(arr)
while lo < hi:
mid = (hi + lo) // 2
if func(arr[mid]):
hi = mid # new search space [lo, mid)
else:
lo = mid + 1 # new search space [mid + 1, hi)
return lo # lo = hi = the first index such that func return True
arr = list(range(20))
func = lambda x: x >= 10
idx = binary_search_left(arr, func)
print(arr[idx]) # 10
```

returns `i`

, such that `arr[:i] == False`

and `arr[i:] == True`

.

```
def binary_search_right(arr, func):
lo, hi = 0, len(arr)
while lo < hi:
mid = (hi + lo) // 2
if not func(arr[mid]):
hi = mid # new search space [lo, mid)
else:
lo = mid + 1 # new search space [mid + 1, hi)
return lo # lo = hi = first index such that func return False
func = lambda x: x <= 10
idx = binary_search_right(arr, func)
print(arr[idx-1]) # 10
```

returns `i`

, such that `arr[:i] == True`

and `arr[i:] == False`

. As a result, `arr[i-1]`

if exist will be the last `True`

value.

### Sample Questions

- 34. Find First and Last Position of Element in Sorted Array
- 410. Split Array Largest Sum
- 1231. Divide Chocolate
- 1618. Maximum Font to Fit a Sentence in a Screen
- 354. Russian Doll Envelopes
- 300. Longest Increasing Subsequence
- 1146. Snapshot Array
- 981. Time Based Key-Value Store
- 528. Random Pick with Weight
- 852. Peak Index in a Mountain Array
- 162. Find Peak Element
- 1901. Find a Peak Element II
- 302. Smallest Rectangle Enclosing Black Pixels
- 4. Median of Two Sorted Arrays