Binary search (bug) - cocoder39/coco39_LC GitHub Wiki

Use case:

  1. index is bounded and items are sorted
  2. items are not sorted, but are within a range. ex Find the Duplicate Number, Kth Smallest Element in a Sorted Matrix

Implementation: there are several places we need pay attention when coding binary search.

  1. while condition and its impact on shrinking the searching range
  • one is using int mid = start + (end - start) / 2 in case of overflow caused by int mid = (start + end) / 2
  • sometimes we use while (start < end), sometimes use while (start + 1 < end). Pay attention to the difference. In the first case, end - start >= 1 inside loop, while end - start >= 2 in second case. The difference really matters.

case 1: mid = start + (end - start) / 2 >= start + 1 / 2 = start, thus it can happen that mid == start. Hence inside the binary search, update start with start = mid may cause run time error because searching space is not reduced.

case 2: 'mid = start + (end - start) / 2 >= start + 2 /2 > start', getting rid or above problem.

Since start + (end - start) > start + (end - start) / 2, end > mid in both cases

template 1

int start = 0, end = n - 1; //[start, end]
while (start + 1 < end) //start + 1 == end when breaking 
int mid = start + (end - start) / 2;

both start = mid and end = mid are bug-free updating. check both start and end at the end

template 2

start = 0, end = n; //[start, end)
while (start < end) //start == end when breaking

maintain the open/close of searching range when updating start and end. start = mid + 1, end = mid, end = mid + 1 are fine, but be careful about start = mid, where mid should come from mid = start + (end - start + 1) / 2 rather than mid = start + (end - start) / 2. return start at the end.

  1. while condition overflow start + 1 < end or start + 2 < end could be overflow,( so we need return the target as soon as we find the target in the while loop) , or change it to end - start > 1

3 .pay attention to left and right boundaries. The final result might not be either left or right

high - low > 1 =====> low < mid = low + (high - low) / 2 < high

  1. high - low >= 2 ====> low + (high - low) / 2 > low
  2. suppose high - low = 2k or 2k+1 where k >= 1, then high - mid = high - low - (high - low) / 2 == (high - low) - (high-low)/2 >= 2k - k = k >=1 so high > mid

a template

while low + 1 < high: # at least 3 elements 
            mid = low + (high - low) // 2 # low+1 <= mid <= high-1
            if nums[mid-1] < nums[mid] > nums[mid+1]:
                return mid
            elif nums[mid] < nums[mid-1]:
                high = mid # don't use mid-1 to rule out mid since mid-1 may be equal to low (e.g., high == low), which is problematic as we assume high and low are different at the end
            else: # nums[mid] < nums[mid+1]:
                low = mid
        
if nums[low] < nums[high]:
            return high
return low