Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Binary Search

Search a sorted array for a target value in O(log n) time. A step-by-step solution in JavaScript and Python, with a walkthrough and pitfalls.

easyPattern: Binary Search

Updated Short read: 4 min read

Approaches at a glance

ApproachTimeSpace
Linear searchO(n)O(1)
Binary searchO(log n)O(1)

The problem

You are given an array of distinct integers sorted in ascending order, and a target value. Return the index of the target, or -1 if it is not in the array. The solution must run in O(log n) time.

numbers = [-1, 0, 3, 5, 9, 12], target = 9   →  4
numbers = [-1, 0, 3, 5, 9, 12], target = 2   →  -1

Check each element in turn.

JavaScript

function linearSearch(numbers, target) {
  for (let i = 0; i < numbers.length; i++) {
    if (numbers[i] === target) return i;
  }
  return -1;
}

Python

def linear_search(numbers, target):
    for i, value in enumerate(numbers):
        if value == target:
            return i
    return -1

This is correct, and it is the only option for unsorted data. But it does not use the sorted order and does not meet the required running time.

Time O(n). Space O(1).

Because the array is sorted, comparing the target with the middle element tells you which half the target must be in. Discard the other half and repeat.

JavaScript

function search(numbers, target) {
  let lo = 0;
  let hi = numbers.length - 1;
 
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
 
    if (numbers[mid] === target) return mid;
    if (numbers[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  return -1;
}

Python

def search(numbers, target):
    lo = 0
    hi = len(numbers) - 1
 
    while lo <= hi:
        mid = lo + (hi - lo) // 2
 
        if numbers[mid] == target:
            return mid
        if numbers[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

lo and hi mark the part of the array that could still contain the target, and both ends are included. The loop stops when that part is empty, which is when lo passes hi.

Walkthrough

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

lo hi mid numbers[mid] Action
0 5 2 3 3 < 9, search the right half: lo = 3
3 5 4 9 Found: return 4

With target = 2:

lo hi mid numbers[mid] Action
0 5 2 3 3 > 2, search the left half: hi = 1
0 1 0 -1 -1 < 2, search the right half: lo = 1
1 1 1 0 0 < 2, search the right half: lo = 2
2 1 lo is past hi: return -1

Time O(log n): the range halves on every step, so six elements need at most three comparisons and a million need about twenty. Space O(1).

The reasoning behind the template is in the binary search pattern.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

console.log(search([-1, 0, 3, 5, 9, 12], 9)); // 4
console.log(search([-1, 0, 3, 5, 9, 12], 2)); // -1

Python

print(search([-1, 0, 3, 5, 9, 12], 9))  # 4
print(search([-1, 0, 3, 5, 9, 12], 2))  # -1

The comment after each line is the result you should see.

Common mistakes

  • Writing while (lo < hi) with this template. When one element remains, lo equals hi, and that element still has to be checked.
  • Writing lo = mid or hi = mid. mid has already been checked, so it must be excluded. Otherwise the range can stop shrinking and the loop never ends.
  • Forgetting Math.floor. Without it mid can be a fraction, and numbers[2.5] is undefined.

Original problem: LeetCode 704: Binary Search