[Leetcode Pattern] Binary Search

While binary search seems an ordinary technique, there are many special cases that require some modification of the usual template.

freecodecamp

left converges right (final mid is target)

left may equal to right. mid is the position to find.

e.g. Binary Search

The termination condition is left≤right. When too left (nums[mid]<target), make left more right by assigining left = mid+1. Similarily, when too right (target<nums[mid]), make right more left by assigining right = mid-1.

# template
i, j = 0, len(nums)-1
while i<=j:
    mid = (i+j)//2
    if target==nums[mid]: return mid     
    if target>nums[mid]: i=mid+1
    else: j=mid-1
return -1

e.g. First Bad Version

There may be multiple target (isBadVersion) in the array. To find the min, rather than return when found, keep found res, not break the loop until i>j, and update res when smaller found.

res = min(res, mid)

e.g. Find Peak Element

Compare nums[mid-1], nums[mid] and nums[mid+1].

return mid if nums[mid]>nums[mid+1] and nums[mid]>nums[mid-1]
too left: nums[mid]<nums[mid+1]
too right: nums[mid]<nums[mid-1]

left converges right (final mid leads to target)

We are not searching target but somewhere back or front of target.

e.g. Find Smallest Letter Greater Than Target

The res is nums[x] where nums[x-1] < target < nums[x].

For two directions, check if mid < target < i=mid+1, or j=mid-1< target < mid.

left not converges right (target in array)

Some problems give condition that nums[mid] may be used in next round even it’s not the target to find. Hence, mid cannot be forgone, aka the update of left / right is mid without +/- 1 to keep mid for future use. In this situation, left is unable to converge right because when left+1=right, mid = (left+right)//2 will continue being left. Hence, “if left+1=right…” (or “if mid=left”) is necessary to break the loop when mid cannot shift left / right anymore.

# template
i, j = 0, len(nums)-1
while i<j:
    mid = i+(j-i)//2
    if i+1==j: return or break
    elif too left: i=mid
    elif too right: j=mid

e.g. Capacity To Ship Packages Within D Days

The determinant condition is whether days_needed(mid)<=days.

res is kept and updated
too left: days_needed(mid, days)>days
too right: days_needed(mid, days)<=days