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.
Updated Short read: 4 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Linear search | O(n) | O(1) |
| Binary search | O(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 → -1Approach 1: linear search
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 -1This 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).
Approach 2: binary search
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 -1lo 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)); // -1Python
print(search([-1, 0, 3, 5, 9, 12], 9)) # 4
print(search([-1, 0, 3, 5, 9, 12], 2)) # -1The comment after each line is the result you should see.
Common mistakes
- Writing
while (lo < hi)with this template. When one element remains,loequalshi, and that element still has to be checked. - Writing
lo = midorhi = mid.midhas already been checked, so it must be excluded. Otherwise the range can stop shrinking and the loop never ends. - Forgetting
Math.floor. Without itmidcan be a fraction, andnumbers[2.5]isundefined.
Original problem: LeetCode 704: Binary Search