JavaScript: counting the steps of binary search
Show that searching a sorted array of 1000 items takes at most about ten comparisons.
On this page
JavaScript arrays and loops.
- Show that searching a sorted array of 1000 items takes at most about ten comparisons.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
Binary search looks at the middle element of a sorted range. If it is the target, the search ends. Otherwise the target can only be in one half, so the other half is discarded. The range halves each step, so after k steps at most n / 2^k items remain.
The search ends when the range is empty, which takes at most about log2(n) + 1 steps. For 1000 items that is at most 10, compared with up to 1000 for linear search. The count of steps is deterministic, so it is a reliable way to compare algorithms without timing them.
Code example
function binarySearch(sorted, target) {
let low = 0;
let high = sorted.length - 1;
let steps = 0;
while (low <= high) {
steps++;
const mid = Math.floor((low + high) / 2);
if (sorted[mid] === target) return { index: mid, steps: steps };
if (sorted[mid] < target) low = mid + 1;
else high = mid - 1;
}
return { index: -1, steps: steps };
}
const data = Array.from({ length: 1000 }, (_, i) => i * 2);
const found = binarySearch(data, 1500);
const missing = binarySearch(data, 999);
console.log("1500: index " + found.index + " in " + found.steps + " steps");
console.log("999: index " + missing.index + " in " + missing.steps + " steps");
console.log("bound: " + Math.ceil(Math.log2(data.length + 1)));1500: index 750 in 9 steps 999: index -1 in 9 steps bound: 10
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
function binarySearch(sorted, target) { let low = 0; let high = sorted.length - 1; let steps = 0; while (low <= high) { steps++; const mid = Math.floor((low + high) / 2); if (sorted[mid] === target) return { index: mid, steps: steps }; if (sorted[mid] < target) low = mid + 1; else high = mid - 1; } return { index: -1, steps: steps };} const data = Array.from({ length: 1000 }, (_, i) => i * 2);const found = binarySearch(data, 1500);const missing = binarySearch(data, 999);console.log("1500: index " + found.index + " in " + found.steps + " steps");console.log("999: index " + missing.index + " in " + missing.steps + " steps");console.log("bound: " + Math.ceil(Math.log2(data.length + 1)));Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Look at the middle of the remaining range. | — | — | |
| Too small: discard the lower half. Otherwise discard the upper half. | — | — | |
| The target is found after 9 halvings of the range. | — | 1500: index 750 in 9 steps | |
| An absent value also takes 9 steps here, within the bound. | — | 1500: index 750 in 9 steps 999: index -1 in 9 steps | |
| ceil(log2(1001)) = 10 is the worst-case number of steps. | — | 1500: index 750 in 9 steps 999: index -1 in 9 steps bound: 10 |
Behind the scenes
How JavaScript processes this code
A JavaScript engine parses and runs the source. A function body runs when the function is called. console.log writes to the console.
Cost and common mistakes
O(log n) time and O(1) space.
- Binary search works only on sorted data. On unsorted data it can miss items that are present.
- For very large arrays (low + high) can overflow in some languages. JavaScript numbers are doubles, so it is safe here up to 2^53.
Try it yourself
About how many steps does a sorted array of one million items need?
Reveal answer and reasoning
At most 20 steps, because log2(1,000,000) is about 19.9.