Searching
Binary Search Explained
Written by Swapnil RajaPublished
Binary search is four lines and almost everyone gets it wrong the first time. The logic is easy; the boundaries are where it breaks.
The idea
Look at the middle. If it is the target, done. If the target is larger, everything to the left is irrelevant - discard half the array. Repeat.
Ten million sorted items takes about 24 steps. That is what O(log n) buys you.
The version to memorise
javascript
function binarySearch(sorted, target) {
let low = 0
let high = sorted.length - 1
while (low <= high) {
const mid = Math.floor((low + high) / 2)
if (sorted[mid] === target) return mid
if (sorted[mid] < target) low = mid + 1
else high = mid - 1
}
return -1
}
console.log(binarySearch([1, 3, 5, 7, 9, 11], 7)) // 3
console.log(binarySearch([1, 3, 5, 7, 9, 11], 4)) // -1