Binary Search

calendarDec 13, 2025 · 11 min read · binary-search searching algorithms divide-and-conquer  ·
Share on: linkedincopy

Binary search is an efficient algorithm for finding a target value in a sorted array by repeatedly dividing the search interval in half.

Basic Algorithm

Concept

Compare the target with the middle element:

  • If equal: found
  • If target < middle: search left half
  • If target > middle: search right half

Mathematical Formulation

For a sorted array $A[0 \ldots n-1]$ and target $x$:

$$ \text{BinarySearch}(A, x, \text{left}, \text{right}) = \begin{cases} -1 & \text{if left} > \text{right} \\ \text{mid} & \text{if } A[\text{mid}] = x \\ \text{BinarySearch}(A, x, \text{left}, \text{mid}-1) & \text{if } A[\text{mid}] > x \\ \text{BinarySearch}(A, x, \text{mid}+1, \text{right}) & \text{if } A[\text{mid}] < x \end{cases} $$

where: $$ \text{mid} = \text{left} + \lfloor (\text{right} - \text{left}) / 2 \rfloor $$

Note: Use left + (right - left) / 2 instead of (left + right) / 2 to avoid integer overflow.

 1// BinarySearch finds target in sorted array, returns index or -1
 2func BinarySearch(arr []int, target int) int {
 3    left, right := 0, len(arr)-1
 4    
 5    for left <= right {
 6        // Avoid overflow: left + (right-left)/2
 7        mid := left + (right-left)/2
 8        
 9        if arr[mid] == target {
10            return mid // Found
11        } else if arr[mid] < target {
12            left = mid + 1 // Search right half
13        } else {
14            right = mid - 1 // Search left half
15        }
16    }
17    
18    return -1 // Not found
19}
20
21// Example usage
22func main() {
23    arr := []int{1, 3, 5, 7, 9, 11, 13, 15}
24    fmt.Println(BinarySearch(arr, 7))  // Output: 3
25    fmt.Println(BinarySearch(arr, 6))  // Output: -1
26}

Recursive Implementation

 1func BinarySearchRecursive(arr []int, target, left, right int) int {
 2    if left > right {
 3        return -1
 4    }
 5    
 6    mid := left + (right-left)/2
 7    
 8    if arr[mid] == target {
 9        return mid
10    } else if arr[mid] < target {
11        return BinarySearchRecursive(arr, target, mid+1, right)
12    } else {
13        return BinarySearchRecursive(arr, target, left, mid-1)
14    }
15}

Complexity Analysis

Time Complexity

Recurrence relation: $$ T(n) = T(n/2) + O(1) $$

Solution (by Master Theorem): $$ T(n) = O(\log n) $$

Proof by iteration count: After $k$ iterations, search space is $n / 2^k$. When search space becomes 1: $$ \frac{n}{2^k} = 1 \implies k = \log_2 n $$

Space Complexity

  • Iterative: $O(1)$
  • Recursive: $O(\log n)$ due to call stack

Implementation Variants

1. Find Exact Match

Returns index if found, -1 otherwise.

Invariant: If target exists, it's in [left, right]

2. Find First Occurrence (Lower Bound)

Find the leftmost position where target appears or could be inserted.

Invariant: A[left-1] < target and A[right+1] >= target

 1// LowerBound finds first position where arr[i] >= target
 2// Returns insertion point if target not found
 3func LowerBound(arr []int, target int) int {
 4    left, right := 0, len(arr)
 5    
 6    for left < right {
 7        mid := left + (right-left)/2
 8        
 9        if arr[mid] < target {
10            left = mid + 1
11        } else {
12            right = mid
13        }
14    }
15    
16    return left
17}
18
19// Example
20func main() {
21    arr := []int{1, 2, 2, 2, 3, 4, 5}
22    fmt.Println(LowerBound(arr, 2))  // Output: 1 (first occurrence)
23    fmt.Println(LowerBound(arr, 6))  // Output: 7 (insertion point)
24}

Result:

  • If left < n and A[left] == target: first occurrence at left
  • Otherwise: insertion point is left

3. Find Last Occurrence (Upper Bound)

Find the rightmost position where target appears.

 1// UpperBound finds first position where arr[i] > target
 2func UpperBound(arr []int, target int) int {
 3    left, right := 0, len(arr)
 4    
 5    for left < right {
 6        mid := left + (right-left)/2
 7        
 8        if arr[mid] <= target {
 9            left = mid + 1
10        } else {
11            right = mid
12        }
13    }
14    
15    return left
16}
17
18// FindLastOccurrence returns index of last occurrence or -1
19func FindLastOccurrence(arr []int, target int) int {
20    pos := UpperBound(arr, target) - 1
21    if pos >= 0 && pos < len(arr) && arr[pos] == target {
22        return pos
23    }
24    return -1
25}
26
27// Example
28func main() {
29    arr := []int{1, 2, 2, 2, 3, 4, 5}
30    fmt.Println(FindLastOccurrence(arr, 2))  // Output: 3 (last occurrence)
31}

4. Count Occurrences

 1// CountOccurrences counts how many times target appears
 2func CountOccurrences(arr []int, target int) int {
 3    first := LowerBound(arr, target)
 4    last := UpperBound(arr, target)
 5    
 6    if first < len(arr) && arr[first] == target {
 7        return last - first
 8    }
 9    return 0
10}
11
12// Example
13func main() {
14    arr := []int{1, 2, 2, 2, 3, 4, 5}
15    fmt.Println(CountOccurrences(arr, 2))  // Output: 3
16}

Advanced Variations

1. Search in Rotated Sorted Array

Array is sorted but rotated at some pivot.

Example: [4, 5, 6, 7, 0, 1, 2]

 1func SearchRotated(arr []int, target int) int {
 2    left, right := 0, len(arr)-1
 3    
 4    for left <= right {
 5        mid := left + (right-left)/2
 6        
 7        if arr[mid] == target {
 8            return mid
 9        }
10        
11        // Determine which half is sorted
12        if arr[left] <= arr[mid] {
13            // Left half is sorted
14            if arr[left] <= target && target < arr[mid] {
15                right = mid - 1 // Target in left half
16            } else {
17                left = mid + 1 // Target in right half
18            }
19        } else {
20            // Right half is sorted
21            if arr[mid] < target && target <= arr[right] {
22                left = mid + 1 // Target in right half
23            } else {
24                right = mid - 1 // Target in left half
25            }
26        }
27    }
28    
29    return -1
30}
31
32// Example
33func main() {
34    arr := []int{4, 5, 6, 7, 0, 1, 2}
35    fmt.Println(SearchRotated(arr, 0))  // Output: 4
36}

Time: $O(\log n)$

2. Find Minimum in Rotated Array

 1func FindMin(arr []int) int {
 2    left, right := 0, len(arr)-1
 3    
 4    for left < right {
 5        mid := left + (right-left)/2
 6        
 7        if arr[mid] > arr[right] {
 8            // Minimum is in right half
 9            left = mid + 1
10        } else {
11            // Minimum is in left half (including mid)
12            right = mid
13        }
14    }
15    
16    return arr[left]
17}
18
19// Example
20func main() {
21    arr := []int{4, 5, 6, 7, 0, 1, 2}
22    fmt.Println(FindMin(arr))  // Output: 0
23}

Time: $O(\log n)$

3. Find Peak Element

Element greater than its neighbors.

 1func FindPeakElement(arr []int) int {
 2    left, right := 0, len(arr)-1
 3    
 4    for left < right {
 5        mid := left + (right-left)/2
 6        
 7        if arr[mid] < arr[mid+1] {
 8            // Peak is to the right
 9            left = mid + 1
10        } else {
11            // Peak is to the left (including mid)
12            right = mid
13        }
14    }
15    
16    return left
17}
18
19// Example
20func main() {
21    arr := []int{1, 2, 3, 1}
22    fmt.Println(FindPeakElement(arr))  // Output: 2 (value 3)
23    
24    arr2 := []int{1, 2, 1, 3, 5, 6, 4}
25    fmt.Println(FindPeakElement(arr2))  // Output: 5 (value 6)
26}

Time: $O(\log n)$

4. Search in 2D Matrix

 1// Search2DMatrix searches in row-sorted and column-sorted matrix
 2func Search2DMatrix(matrix [][]int, target int) bool {
 3    if len(matrix) == 0 || len(matrix[0]) == 0 {
 4        return false
 5    }
 6    
 7    m, n := len(matrix), len(matrix[0])
 8    left, right := 0, m*n-1
 9    
10    for left <= right {
11        mid := left + (right-left)/2
12        // Convert 1D index to 2D coordinates
13        row, col := mid/n, mid%n
14        midVal := matrix[row][col]
15        
16        if midVal == target {
17            return true
18        } else if midVal < target {
19            left = mid + 1
20        } else {
21            right = mid - 1
22        }
23    }
24    
25    return false
26}
27
28// Example
29func main() {
30    matrix := [][]int{
31        {1, 3, 5, 7},
32        {10, 11, 16, 20},
33        {23, 30, 34, 60},
34    }
35    fmt.Println(Search2DMatrix(matrix, 3))   // Output: true
36    fmt.Println(Search2DMatrix(matrix, 13))  // Output: false
37}

Time: $O(\log(m \times n))$

Binary Search on Answer

When the answer space is monotonic, binary search can find optimal value.

Pattern

  1. Define search space [left, right]
  2. Define feasibility function canAchieve(mid)
  3. Binary search on the answer

Example: Capacity To Ship Packages Within D Days

Problem: Find minimum ship capacity to ship all packages in D days.

 1func ShipWithinDays(weights []int, days int) int {
 2    // Search space: [max(weights), sum(weights)]
 3    left, right := 0, 0
 4    for _, w := range weights {
 5        if w > left {
 6            left = w
 7        }
 8        right += w
 9    }
10    
11    // Binary search on capacity
12    for left < right {
13        mid := left + (right-left)/2
14        
15        if canShip(weights, days, mid) {
16            right = mid // Try smaller capacity
17        } else {
18            left = mid + 1 // Need larger capacity
19        }
20    }
21    
22    return left
23}
24
25// canShip checks if we can ship with given capacity in days
26func canShip(weights []int, days, capacity int) bool {
27    daysNeeded, currentLoad := 1, 0
28    
29    for _, w := range weights {
30        if currentLoad+w > capacity {
31            daysNeeded++
32            currentLoad = w
33            if daysNeeded > days {
34                return false
35            }
36        } else {
37            currentLoad += w
38        }
39    }
40    
41    return true
42}
43
44// Example
45func main() {
46    weights := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
47    days := 5
48    fmt.Println(ShipWithinDays(weights, days))  // Output: 15
49}

Time: $O(n \log(\text{sum} - \text{max}))$

Example: Koko Eating Bananas

 1func MinEatingSpeed(piles []int, h int) int {
 2    left, right := 1, 0
 3    for _, p := range piles {
 4        if p > right {
 5            right = p
 6        }
 7    }
 8    
 9    for left < right {
10        mid := left + (right-left)/2
11        
12        if canFinish(piles, h, mid) {
13            right = mid // Try slower speed
14        } else {
15            left = mid + 1 // Need faster speed
16        }
17    }
18    
19    return left
20}
21
22func canFinish(piles []int, h, speed int) bool {
23    hours := 0
24    for _, p := range piles {
25        hours += (p + speed - 1) / speed // Ceiling division
26    }
27    return hours <= h
28}
29
30// Example
31func main() {
32    piles := []int{3, 6, 7, 11}
33    h := 8
34    fmt.Println(MinEatingSpeed(piles, h))  // Output: 4
35}

Time: $O(n \log(\text{max}))$

Mathematical Properties

Number of Comparisons

Best case: 1 (target is at middle)

Worst case: $\lceil \log_2(n+1) \rceil$

Average case: $\log_2 n - 1$

Decision Tree Height

Binary search corresponds to a decision tree of height: $$ h = \lceil \log_2(n+1) \rceil $$

This is optimal for comparison-based search (information-theoretic lower bound).

Search Space Reduction

After $k$ iterations: $$ \text{remaining elements} = \frac{n}{2^k} $$

Common Pitfalls

1. Integer Overflow

Wrong:

1mid := (left + right) / 2  // Can overflow!

Correct:

1mid := left + (right-left)/2  // Safe from overflow

2. Infinite Loop

Problem: mid calculation can cause infinite loop.

Wrong:

1// When left = 1, right = 2, mid = 1 forever
2for left < right {
3    mid := (left + right) / 2
4    if arr[mid] <= target {
5        left = mid  // Infinite loop!
6    }
7}

Correct:

1for left < right {
2    mid := left + (right-left+1)/2  // Rounds up
3    if arr[mid] <= target {
4        left = mid
5    } else {
6        right = mid - 1
7    }
8}

3. Off-by-One Errors

Common mistakes:

  • Using left <= right vs. left < right
  • Updating with mid vs. mid ± 1
  • Return value off by one

Solution: Maintain clear invariants and test boundary cases.

Comparison with Other Search Algorithms

AlgorithmTime (Average)Time (Worst)SpaceRequirement
Binary Search$O(\log n)$$O(\log n)$$O(1)$Sorted array
Linear Search$O(n)$$O(n)$$O(1)$None
Jump Search$O(\sqrt{n})$$O(\sqrt{n})$$O(1)$Sorted array
Interpolation Search$O(\log \log n)$$O(n)$$O(1)$Uniformly distributed
Exponential Search$O(\log n)$$O(\log n)$$O(1)$Unbounded sorted array

Applications

  1. Dictionary lookup: Fast word search
  2. Database indexing: B-tree search
  3. Version control: Git bisect for finding bugs
  4. Debugging: Finding first failing test
  5. Game development: AI decision trees
  6. Numerical methods: Root finding, optimization
  7. Computer graphics: Ray tracing, collision detection

✅ Use when:

  • Data is sorted (or has monotonic property)
  • Need $O(\log n)$ search time
  • Random access is available (arrays)
  • Search space is large

❌ Don't use when:

  • Data is unsorted and sorting cost > search benefit
  • Data structure doesn't support random access (linked lists)
  • Search space is small (linear search is simpler)
  • Need to find all occurrences (may need linear scan anyway)

Related Snippets

  • Binary Tree
    A binary tree is a tree data structure where each node has at most two children, …
  • General Tree
    A tree is a hierarchical data structure consisting of nodes connected by edges, …
  • Heap Data Structure
    A heap is a specialized tree-based data structure that satisfies the heap …
  • Heap Sort
    Heap sort is a comparison-based sorting algorithm that uses a binary heap data …
  • Linked List Operations
    Optimal techniques for common linked list operations using pointer manipulation, …
  • LRU and LFU Cache
    Cache replacement policies determine which items to evict when the cache is …
  • Merge Sort
    Merge sort is a stable, comparison-based sorting algorithm that uses the …
  • Quadtree
    A Quadtree is a tree data structure where each internal node has exactly four …
  • Quick Sort
    Quick sort is an efficient, in-place, comparison-based sorting algorithm that …
  • String Similarity Algorithms
    Algorithms for measuring similarity between strings, used in spell checking, DNA …
  • Terrain & Heightmap Generation
    Procedural terrain generation creates realistic landscapes using mathematical …
  • Trie (Prefix Tree)
    A Trie (pronounced &quot;try&quot;) is a tree-like data structure used to store …
  • Wave Function Collapse
    Wave Function Collapse (WFC) is a procedural generation algorithm that creates …