Description

Bisect is a variation of Binary Search Exact which lets you find the start index and end index for the range that the binary search is looking at.
?

Reach for when

• You want the left/right most value
• You want the next/prev value to the target

Runtime

O(log(n))

Visualization

Pseudocode

Shrink a window [lo, hi) until it collapses onto one spot:
  look at mid
  mid < target  → toss the left half AND mid
  otherwise     → keep mid, toss the right half
  collapse point = first index with value ≥ target
(bisect right: swap < for ≤)

Code

def bisect_left(A, target):
	lo, hi = 0, len(A)
	while lo < hi:
		mid = (lo + hi) // 2
		if A[mid] < target:       # <= for bisect_right
			lo = mid + 1
		else:
			hi = mid
	return lo