Binary Search
Locate a value in a sorted array in O(log n) by halving the search window on every comparison — never scanning what you can eliminate.
Intent & Description
🎯 Intent
Exploit sorted order to eliminate half the remaining candidates on each comparison — reducing a 1-million-element search to roughly 20 comparisons.
📋 Context
You have a sorted array and need fast lookups. Linear search scans every element — O(n) per query. Binary search uses the sorted order to cut the search space in half on every step.
💡 Solution
Compare the target to the middle element. Equal → return the index. Target smaller → discard the right half, repeat on the left. Target larger → discard the left half, repeat on the right. Continue until found or the window collapses to empty.
Real-world Use Case
📌 TL;DR
Halve the search space on every step — O(log n) on sorted data, zero extra memory. If your data is sorted and you’re doing a linear scan, you’re leaving performance on the table.
Advantages
- O(log n) time — 1M elements requires ~20 comparisons
- No extra memory — operates in-place on the input array
- Simple to implement and reason about
Disadvantages
- Data must be sorted first — unsorted input requires an O(n log n) sort upfront
- Frequent insertions or deletions require re-sorting or a different data structure entirely
- Not suitable for linked lists — O(1) random access is required for midpoint lookup
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid; // Found
} else if (arr[mid] < target) {
left = mid + 1; // Search right half
} else {
right = mid - 1; // Search left half
}
}
return -1; // Not found
}
// Usage
const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(sortedArray, 7)); // 3
console.log(binarySearch(sortedArray, 10)); // -1