(EN) Binary Search Mistake Notes

Goal of Binary Search

• Initialize range (or window, scope)
• Evaluate the middle element
• Drop the half

How to return the first true element

Practice: Kth Missing Positive Number

1. Don’t early return
2. Always preserve the true element inside the range

Example code:

// arr is in non-decreasing order.
func binarySearch(arr []int, target int) int {
    lo, hi : 0, len(arr)-1

    for lo < hi {
        mid := (lo + hi) / 2
        val := arr[mid]

        if val < target {
            lo = mid + 1    // you may drop the mid-th element.
        } else if val == target {
            hi = mid        // you must not drop the mid-th element.
        } else {
            hi = mid - 1
        }
    }

    return lo
}

When the boundary value matters

Practice: Find Minimum in Rotated Sorted Array

Consider the case when the range is squeezed into 2 elements.

• Currently the range is [lo, hi], such that hi == lo + 1
• The values are a, b, c := arr[lo], arr[mid], arr[hi]
• Then you should aware that lo == mid and a == b.