📖 Binary Search

Beginner to Intermediate ~15 min read

Looking for a word in a dictionary with 100,000 words? Do you start from page 1 and check every word? No! You open the middle, see if your word comes before or after, then repeat. Each step cuts the search space in half. That's Binary Search - the most elegant algorithm in computer science!

The Dictionary Lookup

Imagine searching for "algorithm" in a dictionary:

The Smart Strategy

Open middle: See "mango" - your word comes BEFORE
Throw away second half: Only search first half
Open middle of first half: See "dog" - your word comes BEFORE again
Repeat: Keep halving until you find it!

Key insight: Each step eliminates HALF the remaining words!

The Power of Halving

Why O(log n) is Amazing

With 1 million items, how many steps? Just 20!

1,000,000 → 500,000 → 250,000 → 125,000 → ...
Each step cuts the problem in half
After 20 steps: down to 1 item!

That's O(log n) - logarithmic time!

See It in Action

Watch how Binary Search eliminates half the array with each comparison:

Understanding the Process

L (Left): Start of search range
R (Right): End of search range
M (Mid): Middle element to compare
Blue boxes: Current search range
Faded boxes: Eliminated from search
Green box: Target found!

The Requirement: Sorted Array

⚠️ Binary Search ONLY Works on Sorted Arrays

Why? We need to know if the target is in the left or right half!

✅ Sorted: [1, 3, 5, 7, 9] - Binary Search works!
❌ Random: [5, 1, 9, 3, 7] - Binary Search fails!

If your array isn't sorted, either sort it first (O(n log n)) or use Linear Search (O(n)).

The Code

"""
Binary Search - The Dictionary Lookup
Most important searching algorithm!
Time: O(log n), Space: O(1) iterative / O(log n) recursive
Requirement: Array must be SORTED
"""

def binary_search_iterative(arr, target):
    """
    Iterative Binary Search - Recommended approach
    More efficient (no recursion overhead)
    Space: O(1)
    """
    left = 0
    right = len(arr) - 1
    steps = 0
    
    print(f"Searching for {target} in {arr}")
    print(f"Array size: {len(arr)}\n")
    
    while left <= right:
        steps += 1
        # Avoid integer overflow: mid = left + (right - left) // 2
        mid = (left + right) // 2
        
        print(f"Step {steps}:")
        print(f"  Range: [{left}:{right}] (size: {right - left + 1})")
        print(f"  Mid index: {mid}, Mid value: {arr[mid]}")
        
        if arr[mid] == target:
            print(f"  ✓ FOUND at index {mid}!")
            print(f"\nTotal comparisons: {steps}")
            return mid
        elif arr[mid] < target:
            print(f"  {arr[mid]} < {target}, search RIGHT half")
            left = mid + 1
        else:
            print(f"  {arr[mid]} > {target}, search LEFT half")
            right = mid - 1
        print()
    
    print(f"  ✗ NOT FOUND")
    print(f"Total comparisons: {steps}")
    return -1

def binary_search_recursive(arr, target, left=None, right=None, steps=0):
    """
    Recursive Binary Search - Elegant but uses stack space
    Space: O(log n) due to recursion
    """
    if left is None:
        left = 0
        right = len(arr) - 1
        print(f"Searching for {target} in {arr}")
        print(f"Array size: {len(arr)}\n")
    
    if left > right:
        print(f"  ✗ NOT FOUND")
        print(f"Total comparisons: {steps}")
        return -1
    
    steps += 1
    mid = (left + right) // 2
    
    print(f"Step {steps}:")
    print(f"  Range: [{left}:{right}] (size: {right - left + 1})")
    print(f"  Mid index: {mid}, Mid value: {arr[mid]}")
    
    if arr[mid] == target:
        print(f"  ✓ FOUND at index {mid}!")
        print(f"\nTotal comparisons: {steps}")
        return mid
    elif arr[mid] < target:
        print(f"  {arr[mid]} < {target}, search RIGHT half\n")
        return binary_search_recursive(arr, target, mid + 1, right, steps)
    else:
        print(f"  {arr[mid]} > {target}, search LEFT half\n")
        return binary_search_recursive(arr, target, left, mid - 1, steps)

def binary_search_first_occurrence(arr, target):
    """
    Find FIRST occurrence of target
    Useful when array has duplicates
    """
    left, right = 0, len(arr) - 1
    result = -1
    
    print(f"Finding FIRST occurrence of {target} in {arr}\n")
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            result = mid  # Found, but keep searching left
            right = mid - 1
            print(f"Found at {mid}, searching left for first occurrence...")
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    if result != -1:
        print(f"✓ First occurrence at index {result}")
    else:
        print(f"✗ Not found")
    return result

def binary_search_last_occurrence(arr, target):
    """
    Find LAST occurrence of target
    Useful when array has duplicates
    """
    left, right = 0, len(arr) - 1
    result = -1
    
    print(f"Finding LAST occurrence of {target} in {arr}\n")
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            result = mid  # Found, but keep searching right
            left = mid + 1
            print(f"Found at {mid}, searching right for last occurrence...")
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    if result != -1:
        print(f"✓ Last occurrence at index {result}")
    else:
        print(f"✗ Not found")
    return result

# Example 1: Basic Binary Search (Iterative)
print("=" * 70)
print("Example 1: Iterative Binary Search")
print("=" * 70)
arr1 = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target1 = 7
result1 = binary_search_iterative(arr1, target1)

# Example 2: Recursive Binary Search
print("\n" + "=" * 70)
print("Example 2: Recursive Binary Search")
print("=" * 70)
arr2 = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
target2 = 14
result2 = binary_search_recursive(arr2, target2)

# Example 3: Target not found
print("\n" + "=" * 70)
print("Example 3: Target Not Found")
print("=" * 70)
arr3 = [1, 3, 5, 7, 9]
target3 = 6
result3 = binary_search_iterative(arr3, target3)

# Example 4: Large array (shows power of O(log n))
print("\n" + "=" * 70)
print("Example 4: Large Array (1000 elements)")
print("=" * 70)
arr4 = list(range(1, 1001, 1))  # [1, 2, 3, ..., 1000]
target4 = 789
print(f"Array: [1, 2, 3, ..., 1000] ({len(arr4)} elements)")
print(f"Target: {target4}\n")
result4 = binary_search_iterative(arr4, target4)
print(f"\nNote: Only {10} comparisons for 1000 elements! (vs 789 for linear search)")

# Example 5: First and Last Occurrence
print("\n" + "=" * 70)
print("Example 5: First and Last Occurrence (Duplicates)")
print("=" * 70)
arr5 = [1, 2, 2, 2, 3, 4, 4, 5, 5, 5, 5, 6]
target5 = 5
first = binary_search_first_occurrence(arr5, target5)
print()
last = binary_search_last_occurrence(arr5, target5)
if first != -1:
    print(f"\nOccurrences of {target5}: indices [{first}:{last+1}] = {arr5[first:last+1]}")

# Comparison: Linear vs Binary Search
print("\n" + "=" * 70)
print("Comparison: Linear Search vs Binary Search")
print("=" * 70)

def linear_search(arr, target):
    """Linear search for comparison"""
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

sizes = [10, 100, 1000, 10000, 100000, 1000000]
print(f"{'Size':<12} {'Linear (worst)':<15} {'Binary (worst)':<15} {'Speedup':<10}")
print("-" * 60)

for size in sizes:
    linear_worst = size
    binary_worst = size.bit_length()  # log2(size) + 1
    speedup = linear_worst / binary_worst if binary_worst > 0 else 0
    print(f"{size:<12,} {linear_worst:<15,} {binary_worst:<15} {speedup:>8.0f}x")

print("\n" + "=" * 70)
print("Key Insights:")
print("=" * 70)
print("✓ Binary Search: O(log n) - logarithmic time")
print("✓ Requires: SORTED array")
print("✓ Best case: O(1) - middle element")
print("✓ Worst case: O(log n) - still very fast!")
print("✓ Space: O(1) iterative, O(log n) recursive")
print("✓ Real-world: Used in databases, libraries, games")
print("✓ Interview: MUST KNOW algorithm!")
print("\nBinary Search is 50,000x faster than Linear for 1M elements!")

Output

Click Run to execute your code

Iterative vs Recursive: Both have O(log n) time, but iterative uses O(1) space while recursive uses O(log n) space for the call stack. Iterative is recommended for production!

Quick Quiz

Why is Binary Search O(log n) and not O(n)?

Show answer
Each comparison eliminates HALF the remaining elements. How many times can you halve n until you reach 1? log₂(n) times! For 1 million elements, that's only 20 comparisons. Linear search would need up to 1 million!
What's the common mistake: mid = (left + right) / 2?

Show answer
Integer overflow! If left and right are large, their sum might overflow. Safe version: mid = left + (right - left) / 2. This avoids overflow while giving the same result.

Why O(log n)?

Let's understand logarithmic time complexity:

Array Size	Linear Search	Binary Search	Speedup
10	10	4	2.5x
100	100	7	14x
1,000	1,000	10	100x
1,000,000	1,000,000	20	50,000x
1,000,000,000	1,000,000,000	30	33,000,000x

✅ The Magic of Logarithms

Doubling the input only adds ONE more step!

1,000 elements: 10 steps
2,000 elements: 11 steps (just +1!)
1,000,000 elements: 20 steps
2,000,000 elements: 21 steps (just +1!)

This is why Binary Search scales beautifully to massive datasets!

Common Pitfalls

❌ Pitfall 1: Integer Overflow

Wrong: mid = (left + right) / 2

Right: mid = left + (right - left) / 2

If left and right are large (e.g., near 2 billion), their sum can overflow!

❌ Pitfall 2: Infinite Loop

Wrong: right = mid (can loop forever)

Right: right = mid - 1

Always move the pointer PAST the mid to avoid infinite loops!

❌ Pitfall 3: Off-by-One Error

Wrong: while left < right

Right: while left <= right

Use <= to handle the case when left and right point to the same element!

Real-World Applications

Where Binary Search is Used

Databases: B-tree indexes use binary search variant
Java: Arrays.binarySearch()
Python: bisect module
C++: std::binary_search()
Git: git bisect finds bugs in commit history
Games: Pathfinding optimizations
Libraries: Finding books, contacts, any sorted data

Binary Search vs Linear Search

Feature	Linear Search	Binary Search
Time Complexity	O(n)	O(log n) ✓
Space Complexity	O(1) ✓	O(1) iterative ✓
Requirement	Any array ✓	Sorted array only
Best Case	O(1) - first element	O(1) - middle element
Worst Case	O(n)	O(log n) ✓
Use When	Small or unsorted	Large and sorted ✓

The Trade-off

Binary Search is faster BUT requires sorted data.

If data is already sorted: Use Binary Search!
If sorting cost < search savings: Sort then Binary Search
If data is unsorted and small: Linear Search is fine

💡 Key Takeaway

Binary Search is the most important searching algorithm:

✅ O(log n) - logarithmic time complexity
✅ 50,000x faster than linear for 1M elements
✅ Foundation for many interview problems
✅ Used everywhere in production code
⚠️ Requires sorted array
⚠️ Watch for overflow and off-by-one errors

Master Binary Search - it's essential for every programmer!

Summary

The 3-Point Binary Search Guide

Strategy: Divide and conquer - eliminate half each step
Complexity: O(log n) - 20 steps for 1 million items!
Requirement: Array must be sorted

Interview tip: Binary Search is a MUST KNOW. Practice iterative and recursive versions. Know the variants (first/last occurrence, rotated array). Mention O(log n) and the sorted requirement!

What's Next?

You've mastered Binary Search! Next: Linear Search - the baseline searching algorithm for comparison.

Practice: Implement Binary Search from scratch. Try the variants: find first occurrence, find last occurrence, search in rotated sorted array!

Previous Tim Sort

Next Linear Search