Binary Search Applications

Binary search isn't just about finding elements in arrays. Once you understand the core principle—eliminate half the possibilities with each decision—you start seeing opportunities to use it everywhere.

The real power of binary search comes when you realize it's not really about arrays at all. It's about search spaces. Any time you can frame a problem so that you can test a candidate solution and determine which half of the remaining space to search, you can use binary search.

Binary Search on the Answer

Here's a mind-bending idea: what if instead of searching for a value in an array, you search for the answer itself?

Take this problem: you have a pile of bananas and you need to finish them in h hours. Each hour, you can eat up to k bananas. What's the minimum eating speed k that lets you finish in time?

You could try k=1, k=2, k=3, and so on. But that's linear search on the answer space.

Or you could binary search on k. The minimum is 1 (you can always eat 1 banana per hour). The maximum is the size of the largest pile (eat the whole pile in one hour). Between 1 and max_pile, there's a point where k starts being fast enough. Binary search finds that point.

def min_eating_speed(piles, h):
    def can_finish(k):
        # Can we finish all piles in h hours at speed k?
        hours = sum((pile + k - 1) // k for pile in piles)  # Ceiling division
        return hours <= h
    
    left, right = 1, max(piles)
    
    while left < right:
        mid = (left + right) // 2
        
        if can_finish(mid):
            right = mid  # This speed works, try slower
        else:
            left = mid + 1  # Too slow, need faster
    
    return left

The key insight: speeds form a monotonic sequence. If speed k works, all speeds greater than k also work. If speed k doesn't work, no speed less than k will work. That monotonicity is what makes binary search applicable.

Finding Square Roots

You can use binary search to compute square roots without Newton's method:

def sqrt(n, precision=0.001):
    if n < 1:
        return binary_search_sqrt(n, 0, 1, precision)
    return binary_search_sqrt(n, 0, n, precision)

def binary_search_sqrt(n, left, right, precision):
    while right - left > precision:
        mid = (left + right) / 2
        
        if mid * mid == n:
            return mid
        elif mid * mid < n:
            left = mid
        else:
            right = mid
    
    return (left + right) / 2

We're binary searching on the range [0, n] for the value x where x² = n. Each comparison tells us whether x is too big or too small, letting us eliminate half the range.

Finding Peak Elements

An array has a "peak" if an element is greater than its neighbors. You can find a peak in O(log n) time with binary search:

def find_peak(arr):
    left, right = 0, len(arr) - 1
    
    while left < right:
        mid = (left + right) // 2
        
        if arr[mid] < arr[mid + 1]:
            # Peak must be to the right
            left = mid + 1
        else:
            # Peak is at mid or to the left
            right = mid
    
    return left

Why does this work? If arr[mid] < arr[mid+1], we know there's an upward slope to the right. Since the array ends at some point, that slope must eventually go down, creating a peak somewhere to the right. Conversely, if arr[mid] >= arr[mid+1], mid itself might be a peak, or the peak is to the left.

Allocating Pages

Here's a classic problem: you have n books with varying page counts, and k students. Each student must read some consecutive books. How do you distribute the books to minimize the maximum number of pages any student has to read?

This is binary search on the answer. The minimum possible max is the size of the largest book (one student gets just that book). The maximum possible max is the sum of all pages (one student gets everything). The answer is somewhere in between.

def allocate_books(books, k):
    def can_allocate(max_pages):
        # Can we allocate books so no student reads more than max_pages?
        students = 1
        current_pages = 0
        
        for pages in books:
            if pages > max_pages:
                return False  # Single book too large
            
            if current_pages + pages > max_pages:
                # Give current batch to a student, start new batch
                students += 1
                current_pages = pages
                
                if students > k:
                    return False
            else:
                current_pages += pages
        
        return True
    
    left, right = max(books), sum(books)
    
    while left < right:
        mid = (left + right) // 2
        
        if can_allocate(mid):
            right = mid  # This max works, try smaller
        else:
            left = mid + 1  # Too small, need larger max
    
    return left

Again, the answer space is monotonic: if max_pages = X works, any value larger than X also works. If X doesn't work, no value smaller than X works.

Finding in Infinite Arrays

What if you don't know the array size? Imagine an infinite sorted array. You can't set right = len(arr) - 1 because you don't know where it ends.

The trick: exponentially expand your search range until you overshoot, then binary search.

def search_infinite(arr, target):
    # Find a range that contains the target
    left, right = 0, 1
    
    while arr[right] < target:
        left = right
        right *= 2  # Exponential expansion
    
    # Now binary search in [left, right]
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

The initial expansion takes O(log k) where k is the target's actual position. The binary search also takes O(log k). Total: O(log k), which is better than O(k) for linear search.

Searching in Bitonic Arrays

A bitonic array increases then decreases: [1, 3, 8, 12, 4, 2]. To search it:

Find the peak (the max element) using binary search
Binary search the increasing part
Binary search the decreasing part (with reversed comparison)

def search_bitonic(arr, target):
    # Find peak
    peak = find_peak_bitonic(arr)
    
    # Search left (increasing) part
    index = binary_search(arr, target, 0, peak, ascending=True)
    if index != -1:
        return index
    
    # Search right (decreasing) part
    return binary_search(arr, target, peak + 1, len(arr) - 1, ascending=False)

Three binary searches, all O(log n), still O(log n) total.

The Pattern Recognition

These problems don't look like "search in a sorted array" at first. The skill is recognizing when binary search applies:

Look for monotonicity: If increasing X makes Y increase (or decrease), you can binary search X
Look for predicate functions: If you can write a function is_valid(x) that returns true/false, and the trues and falses are grouped (all falses then all trues, or vice versa), you can binary search
Look for "find the minimum/maximum X such that...": Often a binary search problem in disguise

Real-World Applications

Rate limiting: Binary search to find the optimal request rate

Resource allocation: Minimize maximum load across servers

Cutting materials: Minimize waste when cutting materials to specific lengths

Load balancing: Distribute work to minimize maximum worker load

Game AI: Minimax tree search with pruning

Compiler optimization: Finding optimal register allocation

The Power of O(log n)

These applications show why logarithmic complexity matters. If you're searching a space of a million possibilities:

Linear search: up to 1,000,000 checks
Binary search: at most 20 checks

In production systems handling millions of requests, that difference is the difference between a system that works and one that crashes.

Understanding binary search deeply means recognizing it's not an algorithm—it's a way of thinking. Any time you can eliminate half your options with a single test, you're thinking in binary search terms.