What is Binary Search?
Binary Search is a fast search algorithm that works on sorted arrays by repeatedly halving the search space. Instead of checking every element (linear search), it eliminates half the remaining candidates with each comparison.
Key Idea: If the array is sorted, comparing the middle element
tells you which half your target must be in — ignore the other half.
How It Works
Algorithm (iterative):
1. Set low = 0, high = array.length - 1
2. While low <= high:
a. mid = Math.floor((low + high) / 2)
b. If arr[mid] === target → found! Return mid
c. If arr[mid] < target → target is in right half: low = mid + 1
d. If arr[mid] > target → target is in left half: high = mid - 1
3. If loop ends without returning → target not found, return -1
Visualization
Array: [2, 5, 8, 12, 16, 23, 38, 45, 67, 91]
Target: 23
Step 1: low=0 high=9 mid=4 → arr[4]=16 < 23 → search right
[2, 5, 8, 12, 16, | 23, 38, 45, 67, 91]
^^^^^^^^^^^^^^^^^
Step 2: low=5 high=9 mid=7 → arr[7]=45 > 23 → search left
[23, 38, 45, 67, 91]
^^^^^^^
Step 3: low=5 high=6 mid=5 → arr[5]=23 === 23 → FOUND at index 5!
Linear Search would need 6 comparisons.
Binary Search needed only 3.
Time & Space Complexity
Time Complexity:
- Best Case: O(1) - target is the middle element
- Average Case: O(log n) - halves search space each step
- Worst Case: O(log n) - target not found or at boundary
Space Complexity:
- Iterative: O(1) - only a few variables
- Recursive: O(log n) - call stack depth
Comparison:
Array size | Linear Search | Binary Search
------------|---------------|---------------
10 | 10 steps | 4 steps
1,000 | 1,000 steps | 10 steps
1,000,000 | 1,000,000 | 20 steps
1,000,000,000| 1B steps | 30 steps
Requirement: Array MUST be sorted before binary searching.
JavaScript Implementation
// Iterative Binary Search — O(log n) time, O(1) space
function binarySearch(arr, target) {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2); // Avoid overflow
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
}
// Recursive Binary Search — O(log n) time, O(log n) space
function binarySearchRecursive(arr, target, low = 0, high = arr.length - 1) {
if (low > high) return -1; // Base case: search space exhausted
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);
}
// Usage
const sorted = [2, 5, 8, 12, 16, 23, 38, 45, 67, 91];
console.log(binarySearch(sorted, 23)); // → 5
console.log(binarySearch(sorted, 99)); // → -1
Python Implementation
import bisect # Python's built-in binary search library
def binary_search(arr: list, target) -> int:
"""Iterative binary search. Returns index or -1 if not found."""
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2 # Integer division (no overflow in Python)
if arr[mid] == target:
return mid # Found
elif arr[mid] < target:
low = mid + 1 # Search right half
else:
high = mid - 1 # Search left half
return -1 # Not found
def binary_search_recursive(arr: list, target, low: int = 0, high: int = None) -> int:
"""Recursive binary search."""
if high is None:
high = len(arr) - 1
if low > high:
return -1 # Base case: not found
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, high)
else:
return binary_search_recursive(arr, target, low, mid - 1)
# Using Python's built-in bisect module (fastest option)
def binary_search_builtin(arr: list, target) -> int:
"""Use bisect for O(log n) search on sorted lists."""
index = bisect.bisect_left(arr, target) # Find leftmost insertion point
if index < len(arr) and arr[index] == target:
return index # Found
return -1 # Not found
# Usage
sorted_arr = [2, 5, 8, 12, 16, 23, 38, 45, 67, 91]
print(binary_search(sorted_arr, 23)) # → 5
print(binary_search(sorted_arr, 99)) # → -1
print(binary_search_builtin(sorted_arr, 23)) # → 5
TypeScript Implementation
// Generic Binary Search — works with any comparable type
function binarySearch<T>(
arr: T[],
target: T,
compare: (a: T, b: T) => number = (a, b) => (a < b ? -1 : a > b ? 1 : 0)
): number {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
const cmp = compare(arr[mid], target);
if (cmp === 0) return mid; // Found
if (cmp < 0) low = mid + 1; // arr[mid] < target → search right
else high = mid - 1; // arr[mid] > target → search left
}
return -1; // Not found
}
// Binary search on objects using a key extractor
function binarySearchBy<T, K>(
arr: T[],
target: K,
key: (item: T) => K
): number {
let low = 0;
let high = arr.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
const k = key(arr[mid]);
if (k === target) return mid;
if (k < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}
// Usage
const nums = [2, 5, 8, 12, 16, 23, 38, 45];
console.log(binarySearch(nums, 23)); // → 5
const users = [
{ id: 1, name: 'Alice' },
{ id: 3, name: 'Bob' },
{ id: 7, name: 'Carol' },
{ id: 12, name: 'Dave' },
];
console.log(binarySearchBy(users, 7, u => u.id)); // → 2 (Carol)
Finding Boundaries (Lower / Upper Bound)
# Find the FIRST position where target could be inserted (leftmost index)
def lower_bound(arr: list, target) -> int:
"""Returns index of first element >= target."""
low, high = 0, len(arr)
while low < high:
mid = (low + high) // 2
if arr[mid] < target:
low = mid + 1
else:
high = mid # Don't exclude mid — it might be the answer
return low # Always returns a valid insertion point
# Find the LAST position (rightmost index + 1)
def upper_bound(arr: list, target) -> int:
"""Returns index of first element > target."""
low, high = 0, len(arr)
while low < high:
mid = (low + high) // 2
if arr[mid] <= target:
low = mid + 1
else:
high = mid
return low
# Count occurrences of target in sorted array
def count_occurrences(arr: list, target) -> int:
return upper_bound(arr, target) - lower_bound(arr, target)
# Example
arr = [1, 2, 2, 2, 3, 4, 5]
print(lower_bound(arr, 2)) # → 1 (first 2 is at index 1)
print(upper_bound(arr, 2)) # → 4 (past last 2)
print(count_occurrences(arr, 2)) # → 3 (three 2s)
Binary Search on the Answer
# Binary search isn't just for arrays — search on any monotonic function
# "Find the minimum X such that condition(X) is True"
def binary_search_answer(low: int, high: int, condition) -> int:
"""Find the minimum value in [low, high] where condition is True.
Requires: condition is False for all values before the answer,
and True for all values from the answer onwards.
"""
while low < high:
mid = (low + high) // 2
if condition(mid):
high = mid # mid might be the answer, don't exclude it
else:
low = mid + 1 # mid is too small, exclude it
return low # low == high == answer
# Example: Find minimum speed to eat n piles of bananas in h hours
def min_eating_speed(piles: list[int], h: int) -> int:
def can_eat_all(speed: int) -> bool:
# Total hours needed at this speed
hours = sum(-(-pile // speed) for pile in piles) # Ceiling division
return hours <= h
return binary_search_answer(1, max(piles), can_eat_all)
print(min_eating_speed([3, 6, 7, 11], 8)) # → 4
Common Mistakes
Mistake 1: Integer overflow in mid calculation
❌ mid = (low + high) / 2 # Overflows if low+high > INT_MAX
✅ mid = low + (high - low) / 2 # Safe in all languages
Note: Python integers don't overflow, but other languages do.
Mistake 2: Infinite loop from bad boundary update
❌ high = mid # Can loop forever when low == high
✅ high = mid - 1 # Excludes mid when arr[mid] > target
Mistake 3: Off-by-one in loop condition
❌ while (low < high) # May miss the last element
✅ while (low <= high) # Include equal case
Mistake 4: Searching unsorted data
❌ binarySearch([3, 1, 4, 1, 5], 4) # Undefined behavior
✅ Sort first, or use only on sorted input
Binary Search vs Linear Search
Algorithm | Time | Space | Requirement
----------------|-----------|-------|-------------
Linear Search | O(n) | O(1) | None — works on any array
Binary Search | O(log n) | O(1) | Array must be SORTED
When to use Binary Search:
✓ Array is already sorted (or worth sorting once for many searches)
✓ Large datasets where O(n) is too slow
✓ Finding insertion points or boundaries
✓ "Search on answer" problems with monotonic conditions
When to use Linear Search:
✓ Small arrays (< ~20 elements — overhead not worth it)
✓ Unsorted data and you only search once
✓ Linked lists (binary search requires random access)