Chapter 9: Binary Search - Coding Interview Algorithms

1. Binary Search Fundamentals

📌 When and Where to Use

Sorted arrays: Searching in sorted data
Search space reduction: Finding boundaries or optimal value
Monotonic functions: Finding point where condition changes
Real-world example: Finding element in sorted database, finding insertion point, or binary search on answer

Key Properties

Time Complexity: O(log n) instead of O(n)
Requirement: Data must be sorted (or have monotonic property)
Strategy: Eliminate half of search space at each step

2. Classic Binary Search

Example: Search in Sorted Array

def binary_search(nums, target):
    """
    Binary search in sorted array.
    
    Args:
        nums: Sorted array of integers
        target: Value to search for
    
    Returns:
        Index of target, or -1 if not found
    """
    # Step 1: Initialize search boundaries
    left = 0
    right = len(nums) - 1
    
    # Step 2: Continue while search space is valid
    while left <= right:
        # Step 3: Calculate middle index
        # Use (left + right) // 2 to avoid overflow
        mid = left + (right - left) // 2
        
        # Step 4: Compare with target
        if nums[mid] == target:
            # Step 4a: Found target!
            return mid
        elif nums[mid] < target:
            # Step 4b: Target is in right half
            # Move left boundary to mid + 1
            left = mid + 1
        else:
            # Step 4c: Target is in left half
            # Move right boundary to mid - 1
            right = mid - 1
    
    # Step 5: Target not found
    return -1

Step-by-Step Code Walkthrough:

Step 1 - Initialize: Set left = 0, right = len(nums) - 1 (entire array).

Step 2 - Loop: Continue while left <= right (valid search space).

Step 3 - Calculate Mid: mid = left + (right - left) // 2 (avoids overflow).

Step 4 - Compare:

Step 4a: If nums[mid] == target, found! Return mid
Step 4b: If nums[mid] < target, search right half (left = mid + 1)
Step 4c: If nums[mid] > target, search left half (right = mid - 1)

Step 5 - Not Found: If loop ends, target not in array.

3. Search in Rotated Sorted Array

Example: Find Target in Rotated Array

Problem: Array was sorted but rotated. Find target.

def search_rotated(nums, target):
    """
    Search target in rotated sorted array.
    
    Args:
        nums: Rotated sorted array (e.g., [4,5,6,7,0,1,2])
        target: Value to search for
    
    Returns:
        Index of target, or -1 if not found
    """
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        # Step 1: Check if found
        if nums[mid] == target:
            return mid
        
        # Step 2: Determine which half is sorted
        if nums[left] <= nums[mid]:
            # Step 2a: Left half is sorted
            # Check if target is in left half
            if nums[left] <= target < nums[mid]:
                # Target in left half
                right = mid - 1
            else:
                # Target in right half
                left = mid + 1
        else:
            # Step 2b: Right half is sorted
            # Check if target is in right half
            if nums[mid] < target <= nums[right]:
                # Target in right half
                left = mid + 1
            else:
                # Target in left half
                right = mid - 1
    
    return -1

Step-by-Step Code Walkthrough:

Step 1 - Check Found: If nums[mid] == target, return mid.

Step 2 - Find Sorted Half:

Step 2a: If nums[left] <= nums[mid], left half is sorted
- If target in [nums[left], nums[mid]), search left
- Otherwise, search right
Step 2b: Otherwise, right half is sorted
- If target in (nums[mid], nums[right]], search right
- Otherwise, search left

Key Insight: At least one half is always sorted. Use that to determine which half to search.

4. Find First and Last Position

Example: Search Range

Problem: Find first and last position of target in sorted array.

def search_range(nums, target):
    """
    Find first and last position of target.
    
    Args:
        nums: Sorted array (may contain duplicates)
        target: Value to find
    
    Returns:
        [first_index, last_index] or [-1, -1] if not found
    """
    def find_first(nums, target):
        # Step 1: Binary search for first occurrence
        left, right = 0, len(nums) - 1
        first = -1
        
        while left <= right:
            mid = left + (right - left) // 2
            
            if nums[mid] == target:
                # Step 1a: Found target, but might not be first
                first = mid
                # Step 1b: Continue searching left for earlier occurrence
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        
        return first
    
    def find_last(nums, target):
        # Step 2: Binary search for last occurrence
        left, right = 0, len(nums) - 1
        last = -1
        
        while left <= right:
            mid = left + (right - left) // 2
            
            if nums[mid] == target:
                # Step 2a: Found target, but might not be last
                last = mid
                # Step 2b: Continue searching right for later occurrence
                left = mid + 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        
        return last
    
    # Step 3: Find both positions
    first = find_first(nums, target)
    if first == -1:
        return [-1, -1]
    
    last = find_last(nums, target)
    return [first, last]

Step-by-Step Code Walkthrough:

find_first function:

Step 1a: When nums[mid] == target, save position
Step 1b: Continue searching left (right = mid - 1) to find first occurrence

find_last function:

Step 2a: When nums[mid] == target, save position
Step 2b: Continue searching right (left = mid + 1) to find last occurrence

Step 3 - Combine: Find both first and last positions.

5. Binary Search on Answer

📌 When and Where to Use

Optimization problems: Finding minimum/maximum value that satisfies condition
Monotonic property: If x works, then x+1 works (or vice versa)
Real-world example: Finding minimum capacity, maximum distance, or optimal threshold

Example: Find Minimum in Rotated Array

def find_min_rotated(nums):
    """
    Find minimum element in rotated sorted array.
    
    Args:
        nums: Rotated sorted array
    
    Returns:
        Minimum element
    """
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        
        # Step 1: Compare mid with right
        if nums[mid] > nums[right]:
            # Step 1a: Minimum is in right half
            # Left half is sorted, minimum must be right
            left = mid + 1
        else:
            # Step 1b: Minimum is in left half (including mid)
            # Right half is sorted, minimum is left
            right = mid
    
    # Step 2: left == right, this is the minimum
    return nums[left]

Step-by-Step Code Walkthrough:

Step 1 - Compare:

Step 1a: If nums[mid] > nums[right], minimum is in right half (left = mid + 1)
Step 1b: Otherwise, minimum is in left half including mid (right = mid)

Step 2 - Result: When left == right, we've found the minimum.

📚 Chapter Summary

Classic Binary Search: O(log n) search in sorted array
Rotated Array: Find sorted half, then search appropriately
First/Last Position: Continue searching after finding target
Binary Search on Answer: Search for optimal value that satisfies condition

Key Takeaway: Binary search reduces search space by half at each step. Works on sorted data or when there's a monotonic property. Be careful with boundary conditions (left <= right vs left < right).