Binary Search (LeetCode 704)

The problem

You get an array nums of distinct integers sorted in ascending order, and an integer target. Return the index of target in nums, or -1 if it isn’t there. Your algorithm must run in O(log n) time.

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4

9 sits at index 4.

How to think about it

Start with brute force. Scan left to right and return the index when you see target. That is O(n), and it ignores the one thing the problem hands you: the array is sorted.

What does “sorted” buy you? Look at any single element nums[mid]. If it is smaller than the target, then every element to its left is smaller too, so the target can only be to the right. If it is bigger, the target can only be to the left. One comparison throws away half of what’s left.

The key insight: keep a range that must contain the target, and halve it. Hold lo and hi so that, if the target exists, it is somewhere in nums[lo..hi] (both ends included). Check the middle. Either you found it, or you move lo past mid or hi before mid. When lo > hi, the range is empty and the target isn’t there. Halving from n down to 0 takes about log₂ n steps, so a million elements need about 20 comparisons.

Which pattern is this? Binary search, in its purest form. The tell is a sorted input plus a requirement of O(log n). Learn this closed-interval template exactly: while lo <= hi, lo = mid + 1, hi = mid - 1. Most bugs come from mixing it with other templates.

Approach

1. Set lo = 0 and hi = len(nums) - 1.
2. While lo <= hi:
   • Let mid = (lo + hi) // 2.
   • If nums[mid] == target, return mid.
   • If nums[mid] < target, the target is to the right: lo = mid + 1.
   • Otherwise it is to the left: hi = mid - 1.
3. The range is empty, so return -1.

Solution

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1             # target, if present, is in nums[lo..hi]
    while lo <= hi:                       # range is non-empty
        mid = (lo + hi) // 2
        if nums[mid] == target: return mid
        if nums[mid] < target: lo = mid + 1   # discard mid and everything left
        else: hi = mid - 1                    # discard mid and everything right
    return -1
# binary_search([-1,0,3,5,9,12], 9) -> 4

Dry run

On nums = [-1, 0, 3, 5, 9, 12], target = 9:

Two comparisons instead of five, and the answer is 4.

Complexity

• Time: O(log n). Each iteration at least halves the size of [lo, hi].
• Space: O(1). Just three integers.

Edge cases and pitfalls

• Empty array: hi = -1, the loop never runs, and you return -1.
• < instead of <= in the loop condition skips the last one-element range, so a target at the final position checked is missed.
• lo = mid or hi = mid in this template can loop forever when lo == hi. With the closed interval, always step past mid.
• Overflow: in Java or C++, (lo + hi) / 2 can overflow; write lo + (hi - lo) / 2. Python integers don’t overflow, but interviewers like hearing that you know this.
• Target smaller than everything or bigger than everything both end with an empty range and return -1.

Related problems

• Search Insert Position (LeetCode 35): same search, but return where the target would go.
• Search a 2D Matrix (LeetCode 74): this exact template on a matrix flattened into one index range.
• Search in Rotated Sorted Array (LeetCode 33): the same loop when only half the array is sorted at each step.