Binary Search

Overview

Binary Search is an efficient search algorithm that finds the position of a target value within a sorted array. The algorithm works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

The key requirement for binary search is that the data structure must be sorted. This allows the algorithm to eliminate half of the remaining elements at each step, making it significantly faster than linear search for large datasets. Binary search can be implemented both iteratively and recursively, with the iterative approach generally being preferred for its better space efficiency.

Binary search has a time complexity of O(log n), where n is the number of elements in the array. This logarithmic time complexity makes it extremely efficient for large datasets. The space complexity is O(1) for the iterative implementation and O(log n) for the recursive implementation due to the call stack.

How It Works

The algorithm works by:

Comparing the target with the middle element of the array
If they match, return the index
If the target is less than the middle element, search the left half
If the target is greater than the middle element, search the right half
Repeat until the element is found or the search space is exhausted

Algorithm Pseudocode


BinarySearch(arr, target):
    left = 0
    right = arr.length - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1  # Target not found

Implementation

Iterative Implementation


def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

Recursive Implementation


def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    
    mid = left + (right - left) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

Complexity Analysis

Time Complexity: O(log n) - Each step eliminates half the search space
Space Complexity: O(1) iterative, O(log n) recursive
Best Case: O(1) - Target at the middle
Worst Case: O(log n) - Target not found or at the edge

Common Trends in Problems where Binary Search is Applied

Sorted Arrays: Binary search requires sorted data, making it perfect for problems involving sorted arrays or when you can sort the data first.
Search Space Reduction: Problems where you need to eliminate half the search space at each step naturally fit binary search.
Boundary Finding: Binary search excels at finding boundaries, such as the first or last occurrence of an element, or insertion points.
Optimization Problems: When searching for a minimum or maximum value that satisfies certain conditions, binary search on the answer space is often the solution.
Monotonic Functions: Problems involving monotonic functions (always increasing or decreasing) can often be solved using binary search.

Binary Search Framework

Initialize left and right pointers to define the search space (typically 0 and n-1 for arrays).
Use a while loop that continues while left <= right (or left < right depending on the problem).
Calculate the middle index using left + (right - left) // 2 to avoid integer overflow.
Compare the middle element with the target and adjust the search space accordingly.
Handle edge cases carefully, especially when the target is not found or when dealing with duplicate values.

Search Variations

Finding First/Last Occurrence

When dealing with duplicate values, you might need to find the first or last occurrence of a target:


def find_first_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            result = mid
            right = mid - 1  # Continue searching left
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

Use the Standard Library

Before hand-writing any of these: Python's bisect module implements binary search in C and gets all the edge cases right. Reach for it first.

import bisect

i = bisect.bisect_left(arr, target)    # first index where arr[i] >= target
j = bisect.bisect_right(arr, target)   # first index where arr[i] >  target

found = i < len(arr) and arr[i] == target    # membership
count = j - i                                # number of occurrences of target
bisect.insort(arr, value)                    # insert, keeping the list sorted

# Python 3.10+ accepts a key, so you can search a list of objects directly:
i = bisect.bisect_left(records, target_date, key=lambda r: r.date)

bisect_left and bisect_right together replace most hand-written "find first / find last occurrence" code, including the function above.

Search in Rotated Array

Binary search can be adapted to work with rotated sorted arrays. The trick is that after any split, at least one half is still properly sorted, and you can test which one in O(1):


def search_rotated(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        
        # Left half is sorted
        if arr[left] <= arr[mid]:
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return -1

This version assumes distinct elements. With duplicates it breaks down: when arr[left] == arr[mid] you cannot tell which side is sorted — consider [3, 1, 3, 3, 3] versus [3, 3, 3, 1, 3], which look identical at the endpoints and midpoint. The usual patch is to shrink the window by one (left += 1) when the three values tie, which restores correctness but degrades the worst case to O(n). There is no way around that: with duplicates, the problem genuinely requires linear time in the worst case.

Common Pitfalls

Integer overflow. (left + right) // 2 can overflow in fixed-width languages when both indices are large. Use left + (right - left) // 2, as above. This was a genuine bug in the JDK's Arrays.binarySearch for nine years, and Jon Bentley noted that most binary searches in a published survey were subtly wrong.
Off-by-one in the loop condition. while left <= right with an inclusive right = len(arr) - 1, or while left < right with an exclusive right = len(arr). Mixing the two conventions causes infinite loops or missed elements. Pick one and hold it.
Infinite loops when narrowing. If a branch sets left = mid rather than mid + 1, and mid rounds down to left, the window stops shrinking. When you need left = mid, round the midpoint up: mid = left + (right - left + 1) // 2.
Requires random access. Binary search on a linked list is O(n), because reaching the midpoint costs O(n) — the whole benefit is lost.
The array must actually be sorted. Binary search on unsorted data does not error; it silently returns wrong answers.

Related Search Techniques

Binary search on the answer. The most valuable generalisation. Whenever a predicate is monotonic — false, false, ..., false, true, true, ..., true — you can binary search for the boundary even when there is no array involved. "Find the minimum capacity that ships all packages within D days" is a binary search over capacities, not over an input list.
Exponential (galloping) search: for unbounded or very large ranges, double an index until you overshoot the target, then binary search the bracket you have found. O(log i) where i is the target's position — better than O(log n) when the target is near the front.
Interpolation search: instead of the midpoint, guess where the value should be by linear interpolation. O(log log n) on uniformly distributed data, but degrades to O(n) when the distribution is skewed.
Branchless / Eytzinger layout: a performance technique that stores the array in BFS order so that lookups become cache-friendly and can avoid unpredictable branches. Several times faster than textbook binary search on large arrays.

Related Algorithms

Explore other searching algorithms:

Linear Search - Simple O(n) search for unsorted data
Back to Searching Algorithms Overview