🔍 Binary Search Fundamentals

🎯 What is Binary Search?

Binary search is a divide-and-conquer algorithm that finds the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half.

Precondition: Array must be sorted
Key Idea: Compare target with middle element
Time Complexity: O(log n) — highly efficient!
Space Complexity: O(1) iterative, O(log n) recursive

📌 Sorted Array Required📌 O(log n) Time📌 Divide & Conquer

The Core Idea

Key Insight: By comparing the target with the middle element, we can eliminate half of the remaining elements in each step. This makes binary search exponentially faster than linear search.

The Algorithm:

Step 1 Find the middle element
Step 2 If target == middle → found
Step 3 If target < middle → search left half
Step 4 If target > middle → search right half

# Binary Search - The Foundation
# Search for target in sorted array arr
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # Avoid overflow
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1  # Target not found

# Example:
# arr = [1, 3, 5, 7, 9, 11, 13]
# target = 7
# Step 1: mid = 3, arr[3] = 7 → found at index 3

📝 Classic Binary Search

🎯 Standard Implementation

The classic binary search finds any occurrence of the target in a sorted array. It returns the index of the target if found, otherwise -1.

Iterative: While left ≤ right
Recursive: Function call on subarray
Mid Calculation: left + (right - left) // 2
Edge Cases: Empty array, target smaller/larger than all

# Classic Binary Search - Iterative
def binary_search_iterative(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

# Classic Binary Search - Recursive
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)

# Example:
arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# Search for 23 → returns 5
# Search for 100 → returns -1

🎯 First & Last Occurrence

🎯 Finding Boundaries in Duplicates

When the array contains duplicates, we often need to find the first or last occurrence of the target. This is a common variation of binary search.

First Occurrence: Leftmost index of target
Last Occurrence: Rightmost index of target
Range Query: Find both to get the range

# First Occurrence (Lower Bound)
def 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

# Last Occurrence (Upper Bound)
def last_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
            left = mid + 1  # Continue searching right
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

# Example:
arr = [1, 2, 2, 2, 3, 4, 4, 5, 5, 5]
# first_occurrence(5) → 7
# last_occurrence(5) → 9
# Range: [7, 9] → 3 occurrences

📊 Insert Position & Lower/Upper Bound

🎯 Finding Where to Insert

Often we need to find the position where a target should be inserted to maintain sorted order. This is equivalent to finding the lower bound (first element ≥ target).

Lower Bound: First position where arr[pos] ≥ target
Upper Bound: First position where arr[pos] > target
Insert Position: Lower bound

# Lower Bound (first element >= target)
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 (first element > target)
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

# Insert Position (same as lower_bound)
def search_insert(arr, target):
    return lower_bound(arr, target)

# Example:
arr = [1, 3, 5, 7, 9]
# search_insert(6) → 3 (insert before 7)
# search_insert(0) → 0 (insert at beginning)
# search_insert(10) → 5 (insert at end)

🔄 Search in Rotated Sorted Array

🎯 Finding in a Rotated Array

A rotated sorted array is a sorted array that has been shifted (e.g., [4,5,6,7,0,1,2]). We can still search in O(log n) by identifying which half is sorted.

Key Insight: At least one half is always sorted
Approach: Determine which half is sorted, then search
Duplicate Handling: More complex with duplicates

# Search in Rotated Sorted Array (No Duplicates)
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

# Example:
arr = [4, 5, 6, 7, 0, 1, 2]
# search_rotated(0) → 4
# search_rotated(3) → -1

# With Duplicates (more complex)
def search_rotated_duplicates(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return True
        
        # Handle duplicates: skip equal elements
        if arr[left] == arr[mid] == arr[right]:
            left += 1
            right -= 1
        elif arr[left] <= arr[mid]:
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return False

♾️ Search in Infinite/Unknown Array

🎯 Finding in an Unknown-Sized Array

When the array size is unknown (or infinite), we need to first find a search range, then apply binary search.

Step 1: Exponentially expand the range
Step 2: Double the bound until target is in range
Step 3: Apply binary search within the range
Use Case: Streaming data, unknown length arrays

# Search in Infinite Sorted Array
def search_infinite(arr, target):
    # Step 1: Find bounds
    left, right = 0, 1
    
    # Exponentially increase right until target is in range
    while arr[right] < target:
        left = right
        right *= 2
        # If right exceeds array length, handle appropriately
        try:
            arr[right]
        except IndexError:
            # We reached the end, but target might still exist
            # Use a very large number or handle differently
            right = len(arr) - 1
            break
    
    # Step 2: Binary search in [left, right]
    while left <= right:
        mid = left + (right - left) // 2
        try:
            if arr[mid] == target:
                return mid
            elif arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        except IndexError:
            right = mid - 1  # Adjust if mid is out of bounds
    
    return -1

# Alternative: Search in sorted array of unknown length
# using exponential search (also called doubling search)

📐 Search in 2D Matrix

🎯 Searching in a 2D Matrix

Two common variations: (1) Matrix where each row is sorted, and (2) Matrix where rows and columns are sorted.

Type 1: Each row sorted, first element of each row > last of previous
Type 2: Each row and column sorted (matrix is sorted)
Approach: Treat as 1D array or use row-wise binary search

# Search in 2D Matrix (Type 1: Flattened)
def search_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    
    m, n = len(matrix), len(matrix[0])
    left, right = 0, m * n - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        row = mid // n
        col = mid % n
        
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return False

# Search in 2D Matrix (Type 2: Row & Column sorted)
def search_matrix_rc_sorted(matrix, target):
    if not matrix or not matrix[0]:
        return False
    
    row, col = 0, len(matrix[0]) - 1
    
    while row < len(matrix) and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            row += 1
        else:
            col -= 1
    
    return False

# Example:
matrix = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 60]
]
# search_matrix(3) → True
# search_matrix(13) → False

🧩 With Duplicates

🎯 Handling Duplicate Elements

Binary search with duplicates requires careful handling to find the correct boundary or determine if the target exists.

Find First/Last: Use boundary-finding variants
Count Occurrences: first + last to get range
Rotated with Duplicates: More complex (skip duplicates)

# Count Occurrences of Target
def count_occurrences(arr, target):
    first = first_occurrence(arr, target)
    if first == -1:
        return 0
    last = last_occurrence(arr, target)
    return last - first + 1

# Find Peak in Array with Duplicates
def find_peak_duplicates(arr):
    left, right = 0, len(arr) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] > arr[mid + 1]:
            right = mid
        elif arr[mid] < arr[mid + 1]:
            left = mid + 1
        else:
            # Handle duplicates: adjust search range
            # This is a simplified approach
            if arr[left] == arr[mid] == arr[right]:
                left += 1
                right -= 1
            elif arr[mid] == arr[mid + 1]:
                # Need to check which side might have the peak
                # Complex handling needed
                pass
    
    return left

# Example with duplicates:
arr = [1, 2, 2, 2, 3, 3, 4, 4, 4, 5]
# count_occurrences(4) → 3
# count_occurrences(6) → 0

🎯 Binary Search on Answer Space

🎯 Searching for an Answer, Not an Index

Binary search can be applied to search for a value in the answer space (the range of possible answers) rather than searching in an array.

Monotonic Property: The predicate must be monotonic
Common Problems: K-th element, smallest/largest with condition
Example: Find minimum capacity to ship packages

# Binary Search on Answer Space
# Example: Find the smallest capacity to ship packages within D days
def ship_within_days(weights, days):
    def can_ship(capacity):
        current_weight = 0
        days_needed = 1
        for weight in weights:
            if current_weight + weight > capacity:
                days_needed += 1
                current_weight = 0
            current_weight += weight
        return days_needed <= days
    
    left, right = max(weights), sum(weights)
    
    while left < right:
        mid = left + (right - left) // 2
        if can_ship(mid):
            right = mid
        else:
            left = mid + 1
    
    return left

# Example:
# weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# days = 5
# Minimum capacity: 15

# Other examples:
# - Kth smallest element in sorted matrix
# - Maximum minimum distance in arrays
# - Minimum time to complete tasks
# - Split array largest sum

🌀 Binary Search Variations

Ternary Search: Split into 3 parts (for unimodal functions)
Exponential Search: Jump search + binary search
Interpolation Search: Estimate position (O(log log n) for uniform data)
Jump Search: Block search (O(√n))
Fibonacci Search: Uses Fibonacci numbers for splitting
Binary Search Tree: Tree-based binary search
Bitwise Binary Search: Using bit manipulation

⏱️ Time & Space Complexities

Variant	Time Complexity	Space Complexity	Notes
Classic Binary Search	O(log n)	O(1) iterative, O(log n) recursive	Sorted array
First/Last Occurrence	O(log n)	O(1)	With duplicates
Rotated Sorted Array	O(log n)	O(1)	No duplicates
Rotated with Duplicates	O(log n) worst, O(n) worst-case	O(1)	With duplicates
2D Matrix (Type 1)	O(log(m×n))	O(1)	Flattened view
2D Matrix (Type 2)	O(m + n)	O(1)	Row & column sorted
Infinite Array	O(log n)	O(1)	Exponential expansion
Answer Space	O(log range × f(n))	O(1)	Monotonic predicate

💻 Implementation Details

🎯 Common Pitfalls & Best Practices

Mid Calculation: Use left + (right - left) // 2 to avoid integer overflow
Boundary Conditions: Be careful with left ≤ right vs left < right
Infinite Loops: Ensure mid changes in each iteration
Duplicate Handling: Adjust search range appropriately
Recursive Depth: Recursive version uses O(log n) stack space

# Common Binary Search Templates

# Template 1: Standard (find exact match)
def bs_template1(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

# Template 2: Lower Bound (first >= target)
def bs_template2(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

# Template 3: Upper Bound (first > target)
def bs_template3(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

# Template 4: Answer Space (monotonic predicate)
def bs_template4(predicate, low, high):
    while low < high:
        mid = low + (high - low) // 2
        if predicate(mid):
            high = mid
        else:
            low = mid + 1
    return low

🌍 Real-World Applications

Database Indexes: B-trees use binary search internally
Search Engines: Query matching and ranking
Version Control: Finding which commit introduced a bug (git bisect)
Gaming: AI decision making, pathfinding
Machine Learning: Hyperparameter tuning, learning rate search
Signal Processing: Peak detection, frequency analysis
Optimization: Finding optimal solutions in monotonic spaces
Networking: Routing tables, DNS lookups

📝 Interview Patterns & Problems

🎯 Key Interview Questions

Classic: "Search for target in sorted array"
First/Last: "Find first and last occurrence of target"
Rotated: "Search in rotated sorted array"
Insert Position: "Find where to insert target"
2D Matrix: "Search in a matrix"
Square Root: "Find square root of x" (integer)
Peak Element: "Find a peak in an array"
K-th Element: "Find the k-th smallest element in arrays"
Ship Capacity: "Minimum capacity to ship within D days"
Split Array: "Split array largest sum"

# Interview Problem: Square Root (Integer)
def my_sqrt(x):
    if x < 2:
        return x
    
    left, right = 1, x // 2
    while left <= right:
        mid = left + (right - left) // 2
        if mid * mid == x:
            return mid
        elif mid * mid < x:
            left = mid + 1
        else:
            right = mid - 1
    
    return right

# Interview Problem: Peak Element
def find_peak(arr):
    left, right = 0, len(arr) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] > arr[mid + 1]:
            right = mid
        else:
            left = mid + 1
    
    return left

# Interview Problem: Search Insert Position
def search_insert_position(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