Binary Search Explained: Find Anything in O(log n)

Imagine searching for a word in a dictionary. You wouldn't start at page one and read every entry. You'd open it roughly to the middle, see if your word comes before or after that page, and then repeat on the correct half. In 20 such steps, you could find any word among a million entries.

That's binary search — and it's one of the most powerful ideas in computer science.

The Core Idea

Binary search works on sorted data. At each step, it:

1. Looks at the middle element
2. If it's the target — done!
3. If the target is smaller — search the left half
4. If the target is larger — search the right half
5. Repeat until found (or the search space is empty)

Each comparison eliminates half the remaining elements. This is what makes it so fast.

Step-by-Step Example

Find 7 in [1, 3, 5, 7, 9, 11, 13, 15]:

Step 1: Middle = index 3, value = 7

• Target is 7, middle is 7 — Found it!

That was lucky. Let's try finding 13:

Step 1: Middle = index 3, value = 7

• 13 > 7, search right half: [9, 11, 13, 15]

Step 2: Middle of right half = 11

• 13 > 11, search right half: [13, 15]

Step 3: Middle = 13

• Found it! In just 3 steps out of 8 elements.

A linear search might have needed 7 steps. Binary search needed 3.

The Code

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid          # Found it
        elif arr[mid] < target:
            left = mid + 1      # Search right half
        else:
            right = mid - 1     # Search left half
    
    return -1  # Not found

Simple, elegant, and incredibly efficient.

Why O(log n) Is Extraordinary

The power of binary search comes from logarithmic scaling:

Read that last row again: one billion elements, just 30 comparisons. Every time you double the data, binary search needs only one more step. This is the magic of logarithmic time complexity.

Binary Search vs Linear Search

The key trade-off: binary search is vastly faster but requires sorted data. If your data changes frequently, you need to keep it sorted (or use a data structure like a balanced BST that maintains sorted order).

Common Pitfalls

1. Integer Overflow in Mid Calculation

The classic bug:

# Bad: can overflow in languages with fixed-size integers
mid = (left + right) // 2
 
# Good: avoids overflow
mid = left + (right - left) // 2

In Python this doesn't matter (arbitrary precision integers), but in C, Java, or C++ it's a real bug that existed in Java's standard library for years.

2. Off-by-One Errors

The most common mistakes:

• Using left < right instead of left <= right (misses the case where the target is the only element)
• Not updating left and right correctly (causing infinite loops)
• Forgetting that mid has already been checked

3. Forgetting the Sorted Requirement

Binary search on unsorted data gives wrong results silently. Always verify your data is sorted, or sort it first (O(n log n) for the sort, then O(log n) for each search).

Beyond Basic Search: Powerful Variants

Binary search isn't just for finding exact matches:

Lower Bound (First Occurrence)

Find the first position where a value appears (or where it would be inserted):

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

Upper Bound (Last Occurrence)

Find the position after the last occurrence:

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

Binary Search on Answer

Some problems ask you to find the minimum or maximum value that satisfies a condition. You can binary search on the answer space:

• "What's the minimum speed to finish all tasks in T hours?"
• "What's the maximum size of square that fits in this space?"

This technique shows up constantly in competitive programming and interviews.

Real-World Applications

Binary search is everywhere:

• Database indexing: B-trees use a form of binary search to locate records
• Git bisect: Find which commit introduced a bug by binary searching through history
• IP routing: Route tables use binary search on prefix lengths
• Spell checkers: Binary search through sorted dictionaries
• Version control: Finding the first version where a test fails
• Machine learning: Binary search for optimal hyperparameters (e.g., learning rate)

The Connection to Sorting

Binary search and sorting are deeply connected. You need sorted data for binary search to work, which is why sorting algorithms are so important. If you search the same dataset many times, it pays to sort it once (O(n log n)) and then use binary search (O(log n)) for each query — much better than linear search (O(n)) every time.

Our sorting visualizations show you exactly how algorithms like merge sort and quick sort produce the sorted arrays that make binary search possible.

The Bigger Picture

Binary search embodies a fundamental principle in computer science: if you can eliminate half the problem at each step, you get logarithmic performance. This principle appears everywhere:

• Binary search trees: O(log n) lookups by maintaining sorted structure
• Balanced trees (AVL, Red-Black): Keep the tree balanced for guaranteed O(log n)
• Divide and conquer algorithms: Merge sort, quick sort, and many others

Understanding binary search deeply — not just the algorithm but the principle — gives you a powerful tool for solving problems efficiently.

Practice These Concepts

Put binary search to work with real coding problems:

• Binary Search (LeetCode 704) — Implement binary search from scratch
• Search in Rotated Sorted Array — Apply binary search to a tricky variant
• Median of Two Sorted Arrays — A hard binary search challenge
• Longest Increasing Subsequence — Combine DP with binary search for O(n log n)

Related Articles

• Big O Notation: A Practical Guide for Beginners
• What is an Algorithm? The Complete Beginner's Guide
• Merge Sort Explained with Visualizations
• Quick Sort Explained with Visualizations