Binary Search: Theory and Practice

Binary Search is one of the most fundamental and powerful algorithms in computer science. It efficiently finds an element in a sorted array by repeatedly dividing the search space in half. Understanding binary search deeply will help you solve many complex problems efficiently.

What is Binary Search?

Binary search is a divide-and-conquer algorithm that finds the position of a target value within a sorted array. Instead of checking every element (linear search), binary search eliminates half of the remaining elements at each step.

The Core Idea

Imagine you're looking for a word in a dictionary. You don't start from page 1 and read every word. Instead, you:

1. Open the dictionary to the middle
2. Compare the word you're looking for with the word on that page
3. If your word comes before, search the left half; if after, search the right half
4. Repeat until you find the word or determine it's not in the dictionary

This is exactly how binary search works!

Why Binary Search is Important

• Efficiency: O(log n) time complexity vs O(n) for linear search
• Scalability: For 1 million elements, binary search needs ~20 comparisons vs 1 million for linear search
• Foundation: Many advanced algorithms build upon binary search concepts
• Real-world Applications: Database indexing, version control systems, game development, and more

Understanding the Algorithm Step-by-Step

Prerequisites

The array must be sorted! Binary search only works on sorted data. If the array isn't sorted, you must sort it first (O(n log n)) or use a different approach.

The Algorithm

Binary search maintains two pointers: left and right, which define the current search space. At each step:

1. Calculate the middle index: mid = (left + right) / 2
2. Compare the element at mid with the target
3. If equal, we found it!
4. If target is smaller, search the left half: right = mid - 1
5. If target is larger, search the right half: left = mid + 1
6. Repeat until left > right (target not found)

Visual Representation

Binary Search Animation

Watch how binary search narrows down the search space step by step:

Animation showing binary search finding target value 7 in a sorted array. Source: Wikipedia - Binary Search

Classic Binary Search Implementation

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    
    while (left <= right) {
        // Calculate middle index (prevents overflow)
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;  // Found!
        } else if (nums[mid] < target) {
            left = mid + 1;  // Search right half
        } else {
            right = mid - 1;  // Search left half
        }
    }
    
    return -1;  // Not found
}

Key Implementation Details

• Mid Calculation: Use left + (right - left) / 2 instead of (left + right) / 2 to prevent integer overflow
• Loop Condition: left <= right ensures we check all possible positions
• Boundary Updates: mid + 1 and mid - 1 exclude the current mid from the next search

Real-World Applications

1. Dictionary/Phone Book Lookup

When searching for a word in a sorted dictionary, binary search is the natural approach. For a dictionary with 1 million words, binary search finds any word in at most 20 comparisons.

2. Database Indexing

Database systems use B-trees (a generalization of binary search trees) to quickly locate records. When you query a database by a primary key, it uses binary search principles.

3. Version Control Systems

Git uses binary search to find when a bug was introduced. By checking out different commits and testing, it narrows down the problematic commit efficiently.

4. Game Development

In games, binary search can find the optimal difficulty level, locate items in sorted inventories, or determine collision boundaries.

5. Finding Boundaries

Binary search can find the first or last occurrence of an element, insertion points, or boundaries in sorted data - essential for many algorithms.

Advanced Mathematical Theory

This section provides a rigorous mathematical treatment of binary search, including formal algorithm descriptions, performance analysis, and complexity derivations. Reference: Wikipedia - Binary Search

Formal Algorithm Description

Given a sorted array \(A\) of \(n\) elements with values \(A_0, A_1, A_2, \ldots, A_{n-1}\) such that \(A_0 \leq A_1 \leq A_2 \leq \cdots \leq A_{n-1}\), and a target value \(T\), the binary search algorithm finds the index of \(T\) in \(A\) using the following procedure:

The key mathematical property is that at each iteration, we eliminate half of the remaining search space. This gives us the logarithmic time complexity.

Time Complexity Analysis

Worst-Case Analysis

In the worst case, binary search continues until the search space is reduced to a single element. Let \(k\) be the number of iterations required.

After each iteration, the search space is halved:

• After iteration 1: at most \(\left\lceil \frac{n}{2} \right\rceil\) elements remain
• After iteration 2: at most \(\left\lceil \frac{n}{4} \right\rceil\) elements remain
• After iteration \(k\): at most \(\left\lceil \frac{n}{2^k} \right\rceil\) elements remain

The algorithm terminates when at most 1 element remains:

\[\left\lceil \frac{n}{2^k} \right\rceil \leq 1\]

This implies:

\[\frac{n}{2^k} \leq 1 \implies n \leq 2^k \implies k \geq \log_2(n)\]

Since \(k\) must be an integer, we have:

\[k = \left\lceil \log_2(n) \right\rceil\]

Therefore, the worst-case time complexity is \(O(\log n)\).

Best-Case Analysis

In the best case, the target element is found at the middle position in the first comparison. This gives us \(O(1)\) time complexity.

Average-Case Analysis

For successful searches, we need to calculate the expected number of comparisons. Let \(C(n)\) be the average number of comparisons for an array of size \(n\).

For a successful search, the target can be at any position with equal probability. The number of comparisons needed to find an element at position \(i\) is equal to the depth of that position in the binary search tree representation, which is \(\lfloor \log_2(i) \rfloor + 1\).

The average number of comparisons is:

\[C(n) = \frac{1}{n} \sum_{i=0}^{n-1} (\lfloor \log_2(i+1) \rfloor + 1)\]

For large \(n\), this approximates to:

\[C(n) \approx \log_2(n) - 1 + \frac{1}{n}\]

Therefore, the average-case time complexity is \(O(\log n)\).

Mathematical Derivation of Average Case

For a more precise analysis, consider that binary search can be represented as a binary tree where each node represents a comparison. The number of comparisons needed to find an element is the depth of that element in the tree plus 1.

For an array of size \(n = 2^k - 1\) (a perfect binary tree), the average depth is:

\[\frac{1}{n} \sum_{d=0}^{k-1} d \cdot 2^d = \frac{(k-2)2^k + 2}{2^k - 1}\]

For large \(k\), this simplifies to approximately \(k - 2 = \log_2(n) - 2\).

For general \(n\), the average number of comparisons is approximately:

\[C(n) \approx \log_2(n) - 1\]

Space Complexity Analysis

Binary search uses only a constant amount of extra space regardless of the input size. The algorithm maintains three variables:

• \(L\) (left pointer): \(O(1)\) space
• \(R\) (right pointer): \(O(1)\) space
• \(m\) (middle index): \(O(1)\) space

Therefore, the space complexity is \(O(1)\).

Note: If implemented recursively, the space complexity becomes \(O(\log n)\) due to the call stack, but the iterative version is preferred for its constant space complexity.

Mathematical Properties

Invariant Property

Binary search maintains the following invariant throughout execution:

If the target \(T\) exists in the array, then \(A_L \leq T \leq A_R\) at all times (where \(L\) and \(R\) are the current search boundaries).

This invariant ensures that we never eliminate the portion of the array containing the target.

Monotonicity Property

The search space reduction follows a monotonic pattern. At each step, either:

• \(L\) increases (we eliminate the left half)
• \(R\) decreases (we eliminate the right half)

This ensures that \(L\) and \(R\) converge, and the algorithm terminates when \(L > R\).

Comparison with Other Search Methods

Binary Search vs Linear Search

Binary Search vs Hash Tables

While hash tables offer \(O(1)\) average-case lookup, binary search has advantages:

• Range queries: Binary search can efficiently find elements in a range, while hash tables cannot
• Memory efficiency: Binary search uses less memory overhead
• Ordered operations: Binary search maintains sorted order, enabling operations like finding predecessor/successor
• No hash collisions: Binary search has deterministic performance

Variations and Extensions

Exponential Search

Exponential search extends binary search to unbounded lists. It first finds a range where the target might be, then performs binary search within that range.

Time complexity: \(O(\log i)\) where \(i\) is the position of the target.

Interpolation Search

Interpolation search uses the value of the target to estimate its position, rather than always checking the middle. For uniformly distributed data, it achieves \(O(\log \log n)\) average-case performance.

The position is estimated as:

\[pos = L + \frac{(R - L)(T - A_L)}{A_R - A_L}\]

Fractional Cascading

Fractional cascading is a technique that speeds up binary searches for the same value in multiple sorted arrays. It preprocesses the arrays to enable faster lookups.

Optimality Proof

Binary search is optimal for comparison-based search in sorted arrays. This can be proven using information theory:

To identify one element among \(n\) possibilities, we need at least \(\log_2(n)\) bits of information. Each comparison provides at most 1 bit of information (the element is either less than, equal to, or greater than the target, giving us 3 possible outcomes, but in practice, we typically get 1 bit per comparison in the worst case).

Therefore, any comparison-based search algorithm requires at least \(\lceil \log_2(n) \rceil\) comparisons in the worst case. Since binary search achieves this bound, it is optimal.

Practical Considerations

Integer Overflow Prevention

When calculating the middle index, using \((L + R) / 2\) can cause integer overflow for large arrays. The safe formula is:

\[m = L + \left\lfloor \frac{R - L}{2} \right\rfloor\]

This is mathematically equivalent but prevents overflow.

Branch Prediction

Modern CPUs use branch prediction to improve performance. Binary search's unpredictable branches can hurt performance. Some implementations use branchless comparisons or rearrange code to improve branch prediction.

Cache Performance

Binary search has poor cache locality compared to linear search for small arrays, as it jumps around in memory. For very small arrays (typically less than 64 elements), linear search may be faster due to better cache performance.

Progressive Examples

Level 1: Simple Binary Search

Start with the classic problem: finding an element in a sorted array.

#include <vector>
using namespace std;

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    
    return -1;
}

Example: nums = [1,3,5,7,9,11], target = 7

• Step 1: mid=2, nums[2]=5 < 7, search right → left=3
• Step 2: mid=4, nums[4]=9 > 7, search left → right=3
• Step 3: mid=3, nums[3]=7 == 7, found at index 3!

Level 2: Finding Insertion Position

Find where to insert an element to maintain sorted order.

int searchInsert(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    
    // When loop exits, left is the insertion position
    return left;
}

Key Insight: When the loop exits, left points to the first position where nums[left] >= target, which is exactly where we should insert.

Level 3: Finding Boundaries

Find the first and last occurrence of a target in a sorted array with duplicates.

// Find first occurrence
int findFirst(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            result = mid;
            right = mid - 1;  // Continue searching left
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

// Find last occurrence
int findLast(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            result = mid;
            left = mid + 1;  // Continue searching right
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

Key Insight: When we find the target, we don't stop. Instead, we continue searching in the direction we want (left for first, right for last).

Level 4: Rotated Sorted Array

Search in an array that was sorted but then rotated.

int searchRotated(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) return mid;
        
        // Determine which half is sorted
        if (nums[left] <= nums[mid]) {
            // Left half is sorted
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;  // Target in sorted left half
            } else {
                left = mid + 1;   // Target in unsorted right half
            }
        } else {
            // Right half is sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;   // Target in sorted right half
            } else {
                right = mid - 1;  // Target in unsorted left half
            }
        }
    }
    
    return -1;
}

Key Insight: In a rotated array, one half is always sorted. We check which half is sorted, then determine if the target is in that sorted half. This allows us to eliminate half the search space at each step.

Level 5: Search in 2D Matrix

Search in a matrix where each row and column is sorted.

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if (matrix.empty() || matrix[0].empty()) return false;
    
    int row = 0;
    int col = matrix[0].size() - 1;  // Start from top-right
    
    while (row < matrix.size() && col >= 0) {
        if (matrix[row][col] == target) {
            return true;
        } else if (matrix[row][col] > target) {
            col--;  // All elements in this column are > target
        } else {
            row++;  // All elements in this row are < target
        }
    }
    
    return false;
}

Key Insight: Starting from top-right, we can eliminate an entire row or column at each step, similar to binary search eliminating half the search space.

LeetCode Problems

Practice problems organized by difficulty. Click "Show Solution" to see detailed explanations.

Easy Problems

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

#include <vector>
using namespace std;

int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

Input: nums = [1,3,5,6], target = 5
Output: 2

Input: nums = [1,3,5,6], target = 2
Output: 1

#include <vector>
using namespace std;

int searchInsert(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return left;  // left is the insertion position
}

Input: n = 5, bad = 4
Output: 4
Explanation: call isBadVersion(3) -> false
             call isBadVersion(5) -> true
             call isBadVersion(4) -> true
             Then 4 is the first bad version.

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (isBadVersion(mid)) {
                right = mid;  // First bad is at mid or before
            } else {
                left = mid + 1;  // First bad is after mid
            }
        }
        
        return left;
    }
};

Input: x = 4
Output: 2

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

class Solution {
public:
    int mySqrt(int x) {
        if (x < 2) return x;
        
        int left = 1;
        int right = x / 2;
        
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long square = mid * mid;
            
            if (square == x) {
                return mid;
            } else if (square < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return right;  // Return the smaller value
    }
};

Input: num = 16
Output: true

Input: num = 14
Output: false

class Solution {
public:
    bool isPerfectSquare(int num) {
        if (num < 2) return true;
        
        long left = 1;
        long right = num / 2;
        
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long square = mid * mid;
            
            if (square == num) {
                return true;
            } else if (square < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return false;
    }
};

Medium Problems

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

#include <vector>
using namespace std;

int findFirst(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            result = mid;
            right = mid - 1;  // Continue searching left
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

int findLast(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            result = mid;
            left = mid + 1;  // Continue searching right
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

vector<int> searchRange(vector<int>& nums, int target) {
    return {findFirst(nums, target), findLast(nums, target)};
}

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

#include <vector>
using namespace std;

int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;
        }
        
        // Left half is sorted
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } 
        // Right half is sorted
        else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    
    return -1;
}

Input: nums = [3,4,5,1,2]
Output: 1

Input: nums = [4,5,6,7,0,1,2]
Output: 0

#include <vector>
using namespace std;

int findMin(vector<int>& nums) {
    int left = 0;
    int right = nums.size() - 1;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        // Right half is unsorted, minimum is in right half
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } 
        // Left half is unsorted or both sorted, minimum is in left half
        else {
            right = mid;
        }
    }
    
    return nums[left];
}

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

#include <vector>
using namespace std;

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size();
    int n = matrix[0].size();
    
    int left = 0;
    int right = m * n - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int row = mid / n;
        int col = mid % n;
        int value = matrix[row][col];
        
        if (value == target) {
            return true;
        } else if (value < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return false;
}

Input: matrix = [[1,4,7,11],[2,5,8,12],[3,6,9,16],[10,13,14,17]], target = 5
Output: true

#include <vector>
using namespace std;

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if (matrix.empty() || matrix[0].empty()) {
        return false;
    }
    
    int row = 0;
    int col = matrix[0].size() - 1;  // Start from top-right
    
    while (row < matrix.size() && col >= 0) {
        if (matrix[row][col] == target) {
            return true;
        } else if (matrix[row][col] > target) {
            col--;  // All elements in this column are > target
        } else {
            row++;  // All elements in this row are < target
        }
    }
    
    return false;
}

Hard Problems

Input: nums = [2,2,2,0,1]
Output: 0

Input: nums = [1,3,5]
Output: 1

#include <vector>
using namespace std;

int findMin(vector<int>& nums) {
    int left = 0;
    int right = nums.size() - 1;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else if (nums[mid] < nums[right]) {
            right = mid;
        } else {
            // nums[mid] == nums[right], can't determine which half
            right--;  // Eliminate duplicate
        }
    }
    
    return nums[left];
}

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

#include <vector>
using namespace std;

bool search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return true;
        }
        
        // Handle duplicates
        if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
            left++;
            right--;
            continue;
        }
        
        // Left half is sorted
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } 
        // Right half is sorted
        else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    
    return false;
}

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

#include <vector>
using namespace std;

int findPeakElement(vector<int>& nums) {
    int left = 0;
    int right = nums.size() - 1;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        // If slope is increasing, peak is on the right
        if (nums[mid] < nums[mid + 1]) {
            left = mid + 1;
        } 
        // If slope is decreasing, peak is on the left (including mid)
        else {
            right = mid;
        }
    }
    
    return left;
}

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

#include <vector>
#include <algorithm>
using namespace std;

vector<int> findClosestElements(vector<int>& arr, int k, int x) {
    int left = 0;
    int right = arr.size() - k;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        // If x is closer to arr[mid+k], shrink window from left
        if (x - arr[mid] > arr[mid + k] - x) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return vector<int>(arr.begin() + left, arr.begin() + left + k);
}

Input: nums = [7,2,5,10,8], k = 2
Output: 18
Explanation: There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.

#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

bool canSplit(vector<int>& nums, int maxSum, int k) {
    int count = 1;
    int currentSum = 0;
    
    for (int num : nums) {
        if (currentSum + num > maxSum) {
            count++;
            currentSum = num;
            if (count > k) return false;
        } else {
            currentSum += num;
        }
    }
    
    return true;
}

int splitArray(vector<int>& nums, int k) {
    int left = *max_element(nums.begin(), nums.end());
    int right = accumulate(nums.begin(), nums.end(), 0);
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        if (canSplit(nums, mid, k)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}