Binary Search Explained Simply — With Code Examples in JavaScript, Python & Java
Binary search is the first algorithm that shows you why O(log n) matters. Instead of checking every item in a list, you eliminate half the remaining possibilities with each comparison. This guide explains it from first principles — with visual examples and complete code implementations.
O(log n)
time complexity
1M items
found in max 20 comparisons
O(1)
space complexity (iterative)
~240×
faster than linear on 1M items
The Problem: Why Not Just Check Every Item?
Imagine you have a sorted list of 1,000,000 numbers and you need to find the number 734,291. A linear search checks each item one by one — worst case: 1,000,000 checks.
Binary search uses the fact that the list is sorted: check the middle, eliminate half, repeat. Worst case: just 20 checks for 1 million items.
| Item | Linear Search | Binary Search |
|---|---|---|
| Requirement | Any list (sorted or not) | Must be SORTED |
| 10 items — worst case | 10 comparisons | 4 comparisons |
| 1,000 items — worst case | 1,000 comparisons | 10 comparisons |
| 1,000,000 items — worst case | 1,000,000 comparisons | 20 comparisons |
| Time complexity | O(n) | O(log n) |
| Implementation | Simple | Slightly more complex |
How It Works — The Phonebook Analogy
Think about finding a name in a physical phonebook. You don't start at page 1 and read every name. You open to the middle. If the name you want comes before the middle — flip to the left half. If it comes after — flip to the right half. Repeat until found.
The sorted prerequisite
Binary search only works on sorted data. If your array is unsorted, you must sort it first — but then binary search applies for all future lookups, making the total cost O(n log n) + O(log n) per query.
Why it is O(log n)
Each comparison cuts the search space in half. After k comparisons, only n/2^k elements remain. When n/2^k = 1, you have found it. Solving for k: k = log2(n). For n=1,000,000: log2(1,000,000) is approximately 20.
Three outcomes per step
At each midpoint you get one of three results: found (equal), go left (target is smaller), or go right (target is larger). This three-way branch is the heart of binary search.
Termination condition
The loop ends when low > high — meaning the search space is empty and the target does not exist. This off-by-one is one of the most common implementation bugs.
Mathematical insight
Why log2(n)? Each comparison cuts the search space in half. After k comparisons, you have eliminated all but n/2^k elements. When n/2^k = 1, you have found the answer. Solving: k = log2(n). For n=1,000,000: log2(1,000,000) is approximately 20.
Step-by-Step Walkthrough
Array: [2, 5, 8, 12, 16, 23, 38, 45, 56, 72] — Find: 23
Step 1: low=0, high=9, mid=4
arr[4] = 16. Target 23 > 16, so we search the right half. Set low = mid + 1 = 5. The left half [2, 5, 8, 12, 16] is completely eliminated.
Step 2: low=5, high=9, mid=7
arr[7] = 45. Target 23 < 45, so we search the left half. Set high = mid - 1 = 6. Elements [45, 56, 72] are eliminated.
Step 3: low=5, high=6, mid=5
arr[5] = 23. Target 23 === 23 — FOUND! Return index 5. Total: only 3 comparisons for a 10-element array.
If target was missing: low > high
If we were searching for 99: the low pointer would eventually exceed high. Loop exits, return -1 to indicate not found.
Code — Iterative (Recommended)
function binarySearch(arr, target) {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
// Use Math.floor((low + high) / 2) to avoid overflow
const mid = Math.floor((low + high) / 2);
if (arr[mid] === target) {
return mid; // Found! Return index
} else if (arr[mid] < target) {
low = mid + 1; // Target is in right half
} else {
high = mid - 1; // Target is in left half
}
}
return -1; // Not found
}
// Usage:
const arr = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72];
console.log(binarySearch(arr, 23)); // → 5
console.log(binarySearch(arr, 99)); // → -1def binary_search(arr: list, target: int) -> int:
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid # Found
elif arr[mid] < target:
low = mid + 1 # Right half
else:
high = mid - 1 # Left half
return -1 # Not found
# Usage:
arr = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72]
print(binary_search(arr, 23)) # → 5
print(binary_search(arr, 99)) # → -1
# Python also has bisect in the standard library:
import bisect
idx = bisect.bisect_left(arr, 23)
# bisect returns insertion point, verify arr[idx] == targetpublic class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // Avoids integer overflow
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72};
System.out.println(binarySearch(arr, 23)); // → 5
System.out.println(binarySearch(arr, 99)); // → -1
// Java Arrays has it built-in:
System.out.println(java.util.Arrays.binarySearch(arr, 23)); // → 5
}
}Recursive Version
Iterative vs recursive
function binarySearchRecursive(arr, target, low = 0, high = arr.length - 1) {
if (low > high) return -1; // Base case: not found
const mid = Math.floor((low + high) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, high);
return binarySearchRecursive(arr, target, low, mid - 1);
}Common Mistakes
Potential overflow
// Bug: integer overflow when low + high overflows 32-bit int
const mid = (low + high) / 2; // can overflow in some languagesOverflow-safe
// Safe: avoids overflow by computing distance from low
const mid = Math.floor(low + (high - low) / 2);
// In Python: (low + high) // 2 is fine (arbitrary precision ints)Off-by-one: misses last element
// Bug: wrong termination — loop runs forever
while (low < high) { // missing =
const mid = Math.floor((low + high) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
// When low === high, that element is never checked!Correct termination
// Correct: low <= high ensures single element is checked
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}Advanced: Find First and Last Occurrence
Standard binary search returns any matching index when duplicates exist. To find the first or last occurrence of a value, you need a modified version that keeps searching after finding a match.
// Find FIRST occurrence (leftmost)
function findFirst(arr, target) {
let low = 0, high = arr.length - 1, result = -1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (arr[mid] === target) {
result = mid; // Record this match
high = mid - 1; // Keep searching LEFT for earlier occurrence
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
// Find LAST occurrence (rightmost)
function findLast(arr, target) {
let low = 0, high = arr.length - 1, result = -1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (arr[mid] === target) {
result = mid; // Record this match
low = mid + 1; // Keep searching RIGHT for later occurrence
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
// Example with duplicates:
const arr = [1, 2, 2, 2, 3, 4];
console.log(findFirst(arr, 2)); // → 1
console.log(findLast(arr, 2)); // → 3Binary Search on the Answer Space
Binary search is not just for arrays. A powerful technique is searching the range of valid answers when you need to find the minimum or maximum value that satisfies a condition.
// Find the integer square root (floor) of n
// Instead of searching an array, we binary search the range of possible answers [1, n/2]
function sqrtFloor(n) {
if (n < 2) return n;
let low = 1, high = Math.floor(n / 2), result = 0;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
const square = mid * mid;
if (square === n) return mid; // Perfect square
if (square < n) {
result = mid; // Valid floor candidate — try going larger
low = mid + 1;
} else {
high = mid - 1; // Too large
}
}
return result;
}
console.log(sqrtFloor(16)); // → 4
console.log(sqrtFloor(10)); // → 3 (floor of 3.16...)
console.log(sqrtFloor(25)); // → 5Real-World Uses of Binary Search
Database Indexes
B-tree indexes use a form of binary search. That's why indexed queries are fast and full-table scans are slow. Every WHERE clause on an indexed column is essentially a binary search through the index.
Git Bisect
`git bisect` uses binary search to find the commit that introduced a bug. Halves the commit range with each test — finds a bad commit among 1000 in just 10 steps.
Finding Insertion Point
Where should a new value be inserted to keep a sorted array sorted? Binary search gives the answer in O(log n). Python's bisect module is built on this pattern.
Rotated Array Problems
Common interview variant: find a target in a rotated sorted array [4,5,6,0,1,2,3]. Modified binary search determines which half is sorted and searches appropriately, still in O(log n).
IP Address Routing
Network routers use longest-prefix matching with binary search on sorted routing tables to determine the next hop for packets — billions of lookups per second.
Autocomplete and Spell Check
Dictionary-based autocomplete stores words in sorted order and uses binary search (often combined with trie structures) to find prefix matches instantly.
| Item | Iterative Binary Search | Recursive Binary Search |
|---|---|---|
| Space complexity | O(1) — constant space | O(log n) — call stack frames |
| Risk of stack overflow | None | On very large arrays in some languages |
| Code clarity | Slightly more verbose | More elegant and mathematically natural |
| Performance | Slightly faster (no function call overhead) | Tiny overhead per recursive call |
| Production recommendation | Preferred for production code | Good for learning and interview explanations |
The template to memorize