Binary Search Template

When data is sorted, binary search reduces lookup time from O(n) to O(log n).

Core loop

def search(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Invariants to remember

• Search space is always left..right
• If nums[mid] < target, eliminate left half including mid
• If nums[mid] > target, eliminate right half including mid

Edge cases

• Empty arrays
• One-element arrays
• Target smaller or larger than every element