Master Binary Search: From Basics to Advanced Patterns

Binary search is one of the most powerful algorithmic techniques. When applied correctly, it can reduce O(n) problems to O(log n).

The Basic Pattern

Binary search works on sorted arrays by repeatedly dividing the search space in half:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    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

Finding Boundaries

Often, you need to find the first or last occurrence:

def find_first(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 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

Search in Rotated Array

A common variation is searching in a rotated sorted array:

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

Key Patterns

1. **Standard Search:** Find exact match

2. **Boundary Search:** Find first/last occurrence

3. **Rotated Arrays:** Handle partially sorted data

4. **Search Space:** Apply to non-array problems

Master these patterns, and binary search becomes a powerful tool in your arsenal!