Binary-Search-Variants
Trigger phrase
Phrases:
- Search for largest/smallest value…
- In a sorted array…
Approach
Basic-Binary-Search - more info here
Binary search can find a specific value within a monotonic sequence, but if you phrase something as monotonic cleverly, you can find a best value within logn time.
Most common problems like this:
- Searching for values in rotated array
- Here, our monotonic question is: at indexes i and j, is the array rotated? if yes, continue search right. If not, search left.
- Searching for smallest/largest satisfactory value
- Our monotonic question is: Is our condition satisfied? If yes, optimize further. If no, back off.
Canonical solution
def minInRotatedArr(nums: List[int]):
lo, hi = 0, len(nums)-1
while lo < hi:
mid = lo + (hi-lo)//2
# at indices mid and hi are we rotated?
if nums[mid] <= nums[hi]: # No, we are not rotated here. We went too far
hi = mid # mid is safe to assign to
else: # Yes we are rotated here.
# That means that hi is smaller than mio, and is thus safe to assign mid+1 as a possible min
lo = mid+1 # we also need to reduce search space for low, mid+1 is safe.
return nums[lo]
def smallestSatisfactory(nums: List[int]):
def isSatisfying(current):
return bool # monotonic function based on current
lo, hi = minPossible, maxPossible
while lo < hi:
mid = lo + (hi-lo)//2
# question: does 'mid' satisfy our condition?
satisfying = isSatisfying(mid)
if satisfying: # mid works - could shrink further
hi = mid
else: # mid too slow - exclude it, search higher
lo = mid+1
return loMy gotchas on this pattern
- be very careful about missing a valid solution with the mid+-1 assignment
- be very careful about infinite loops, make sure to reduce search space for lo