Binary Search

The problem

Given a list of integers nums, sorted from smallest to largest with no value repeated, and an integer target, return the position of target in the list, counting from 0. If target is not in the list, return -1. The list may be empty, and then the answer is -1. Aim for O(log n) time, which means far fewer steps than looking at every value.

What to write

function solve(nums: number[], target: number): number

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

Output
4

Input
nums = [-1,0,3,5,9,12]
target = 2

Output
-1

Constraints

0–10,000 distinct sorted integers; integer target.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The list is sorted, and you are asked for O(log n) time. For 10,000 values that means about 14 looks, not 10,000. So you cannot check every value: each look has to rule out many values at once.

2. Hint 2: Ask a smaller question

   In example 1 you are looking for 9 in the list -1, 0, 3, 5, 9, 12. Say the first value you look at is the 3, which is too small. Which other values can you cross off without looking at them?

3. Hint 3: Name the pattern

   One comparison rules out the value you looked at and everything on one side of that value. Look in the middle, and at least half of what is left goes every time. This is binary search on a sorted range. The signals are a sorted list and a request for O(log n) time. Read the lesson on binary search on a sorted range.

4. Hint 4: State the invariant

   Keep a range of positions with two ends, low and high, that both belong to the range. If the target is in the list, its position is always somewhere from low to high. A middle value that is not the target leaves the range, and so does everything on one side of the middle.

5. Hint 5: Sketch the pseudocode

   low = 0, high = last position. While low <= high: mid = (low + high) ÷ 2, rounded down. If the value at mid is the target, return mid. If it is smaller than the target, low = mid + 1. Otherwise high = mid - 1. If the loop ends, return -1.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Maintain an inclusive search interval. Compare target to the middle value and discard the half that cannot contain it.

The slow way

Walk the list from the start and compare each value with the target. Return the position where you find the target, or -1 if you reach the end. This is correct, but it can look at all n values, and it makes no use of the sorted order.

The insight

In a sorted list, one comparison tells you about many values at once. If the middle value is smaller than the target, so is every value to the left of the middle. So a single look at the middle removes at least half of the values that are left.

Step by step

1. The target can only be between the first and last position. Nothing has been ruled out yet, so the range of positions where the target could be is the whole list. Both ends belong to the range, and the search goes on while the range holds at least one position.
2. Look at the value in the middle of the range. Whichever way the comparison goes, the middle leaves at most half of the range to search. A position near one end could leave almost all of the range.
3. The middle value is the target: return its position. No value is repeated, so the target can be at one position only. Once you have found the target, there is nothing left to search.
4. The middle value is too small: the target can only be to its right. The list is sorted, so every value to the left of the middle is smaller still. The middle and everything to its left leave the range.
5. The middle value is too large: the target can only be to its left. Every value to the right of the middle is larger still. The middle and everything to its right leave the range.
6. The range is empty: the target is not in the list. No position is left where the target could be: each one was ruled out by a comparison, or the list was empty to begin with. The answer for that case is -1.

The same numbered steps are the comments in each solution.

function solve(nums, target) {
  // 1. The target can only be between the first and last position
  let l = 0,
    r = nums.length - 1;
  while (l <= r) {
    // 2. Look at the value in the middle of the range
    const m = Math.floor((l + r) / 2);
    // 3. The middle value is the target: return its position
    if (nums[m] === target) return m;
    // 4. The middle value is too small: the target can only be to its right
    if (nums[m] < target) l = m + 1;
    // 5. The middle value is too large: the target can only be to its left
    else r = m - 1;
  }
  // 6. The range is empty: the target is not in the list
  return -1;
}

function solve(nums: number[], target: number): number {
  // 1. The target can only be between the first and last position
  let l = 0,
    r = nums.length - 1;
  while (l <= r) {
    // 2. Look at the value in the middle of the range
    const m = Math.floor((l + r) / 2);
    // 3. The middle value is the target: return its position
    if (nums[m] === target) return m;
    // 4. The middle value is too small: the target can only be to its right
    if (nums[m] < target) l = m + 1;
    // 5. The middle value is too large: the target can only be to its left
    else r = m - 1;
  }
  // 6. The range is empty: the target is not in the list
  return -1;
}

def solve(nums, target):
    # 1. The target can only be between the first and last position
    left, right = 0, len(nums) - 1
    while left <= right:
        # 2. Look at the value in the middle of the range
        mid = (left + right) // 2
        # 3. The middle value is the target: return its position
        if nums[mid] == target:
            return mid
        # 4. The middle value is too small: the target can only be to its right
        if nums[mid] < target:
            left = mid + 1
        # 5. The middle value is too large: the target can only be to its left
        else:
            right = mid - 1
    # 6. The range is empty: the target is not in the list
    return -1

Example 2, traced

Input
nums = [-1,0,3,5,9,12]
target = 2

Output
-1

Why it works

If the target is in the list, its position is always inside the range. A middle value that is too small rules out only itself and smaller values. One that is too large rules out only itself and larger values. The range loses at least one position every round, so the loop ends: on the target, or on an empty range.

Time and space

Time O(log n), extra space O(1). Each round leaves at most half of the range. A list of n values can be halved about log n times before nothing is left: at most 14 rounds for 10,000 values. That is O(log n) time. Only two ends and a middle are stored: O(1) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Keep searching while the range holds at least one position. If you stop as soon as its two ends meet, the one position left is never checked, and a list that holds only the target returns -1.
• When the middle value is not the target, the new range starts one position after the middle or ends one position before it. If the middle stays, the range can stop shrinking and the loop never ends.
• Round the middle down to a whole number. In example 1 the ends are 0 and 5, and half their sum is 2.5. No value sits at position 2.5: JavaScript wrongly returns -1, and Python stops with an error.

Pattern

Binary search on a sorted range.

Keep going