Binary Search Variants

The Idea

Interview problems rarely want any match; they want the first or the last one. So instead of returning on a hit, record it and keep shrinking toward that side. What you get back is a boundary, not an arbitrary index.

Real-World Example

Scanning a cinema's sorted showtimes for the first screening after 7pm. Landing on a 7:30 showing is not the answer yet, because you still have to check earlier and make sure no 7:05 slot exists.

The Code

def first_at_least(nums, target):
    lo, hi, answer = 0, len(nums) - 1, -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] >= target:
            answer = mid      # a candidate...
            hi = mid - 1      # ...but look further left
        else:
            lo = mid + 1
    return answer

print(first_at_least([1, 3, 3, 3, 7], 3))   # 1

nums = [2, 4, 4, 6]
lo, hi, ans = 0, 3, -1
while lo <= hi:
  mid = (lo + hi) // 2
  if nums[mid] >= 4:  ans, hi = mid, mid - 1
  else:               lo = mid + 1
print(ans)