JavaScript: counting the steps of binary search
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.
JavaScript
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)));