Binary Search — Algorithm Visualized
Learn binary search — halve sorted array each step, O(log n) lookup, lo/hi/mid visualizer, code breakdown, and common off-by-one pitfalls.
Introduction
Binary search finds a target in a sorted array by comparing against the middle element and discarding half the search space each step — O(log n) time.
Quick index
| # | Section |
|---|---|
| 1 | How it works |
| 2 | Interactive visualizer |
| 3 | Full implementation |
| 4 | Complexity & pitfalls |
| 5 | Real-life examples |
1. How it works
lo=0, hi=n-1
mid = (lo+hi)/2
if arr[mid] === target → found
if arr[mid] < target → lo = mid+1
else → hi = mid-12. Interactive visualizer
Binary Search — Step Visualizer
Halve the search range each step — requires a sorted array.
Target: 23 · Start
Purple range = active search window
Binary search — sorted array required
const target = 23 let lo = 0, hi = n - 1 mid = floor((lo + hi) / 2)
Halve the search space each step — O(log n).
Time
O(log n)
Space
O(1)
Stable
—
3. Full implementation
function binarySearch(arr, target) {
let lo = 0
let hi = arr.length - 1
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2)
if (arr[mid] === target) return mid
if (arr[mid] < target) lo = mid + 1
else hi = mid - 1
}
return -1
}Function calls with output
// ── Demo calls — output shown on the right ──
const arr = [2, 5, 8, 12, 16, 23, 38, 45]
binarySearch(arr, 23) // → 5
binarySearch(arr, 2) // → 0
binarySearch(arr, 99) // → -14. Complexity & pitfalls
| Metric | Value |
|---|---|
| Time | O(log n) |
| Space | O(1) iterative |
| Prerequisite | Sorted array |
5. Real-life examples
| Scenario | Why binary search |
|---|---|
| Dictionary / phone book lookup | Words sorted alphabetically — open to middle, discard half |
| Git bisect | Find commit that introduced bug — sorted history, halve each step |
| Price filter on sorted catalog | Products sorted by price — find first item ≥ budget |
| Autocomplete index | Prefix tree often backed by sorted string arrays |
| Database B-tree index | Each node splits sorted keys — binary search within node |
E-commerce price filter
Products sorted by price — find first item at or above $50 budget.
Products sorted ascending by price.
Real-world implementation
function binarySearch(arr, target) {
let lo = 0, hi = arr.length - 1
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2)
if (arr[mid] === target) return mid
if (arr[mid] < target) lo = mid + 1
else hi = mid - 1
}
return -1
}
function lowerBoundByPrice(products, minPrice) {
let lo = 0, hi = products.length
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2)
if (products[mid].price < minPrice) lo = mid + 1
else hi = mid
}
return lo < products.length ? products[lo] : null
}Full working code for the scenario above.
Function calls with output
// ── Function calls with output ──
const products = [
{ name:"A", price:10 }, { name:"B", price:45 },
{ name:"C", price:55 }, { name:"D", price:99 }
]Side output shows return value after each call — step through to trace execution.
Summary
Binary search turns sorted lookup from O(n) to O(log n) — foundation for binary search on answer, lower/upper bound, and rotated array variants.
Next reads: Linear Search · Big O Notation
Subscribe to my newsletter
Stay up to date and get notified when I share new contents.
No spam ever, unsubscribe anytime