Binary Search

Binary Search efficiently finds a target value in a sorted array by repeatedly dividing the search space in half. It can also be used to find optimal values in monotonic search spaces.

When to Use

Array is sorted (or can be sorted)
Problem asks to find a target or boundary
Search space is monotonic
Problems asking for 'minimum/maximum value that satisfies condition'

Common Patterns

Standard Binary Search

Find exact target in sorted array

Example: Search in rotated sorted array

Binary Search on Answer

Find optimal value in monotonic search space

Example: Koko eating bananas, capacity to ship packages

Finding Boundaries

Find first/last occurrence or insertion position

Example: First bad version, search insert position

Code Templates

Python

# Standard binary search
def binary_search(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

# Binary search on answer template
def binary_search_answer(arr):
    def feasible(value):
        # Check if value satisfies the condition
        pass
    
    left, right = min_possible, max_possible
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if feasible(mid):
            result = mid
            # Search for better answer
            right = mid - 1  # or left = mid + 1
        else:
            left = mid + 1   # or right = mid - 1
    
    return result

# Find leftmost/rightmost boundary
def find_boundary(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
            # Use left = mid + 1 for rightmost
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

C++

// Standard binary search
int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

// Binary search on answer template
int binarySearchAnswer(vector<int>& arr) {
    auto feasible = [&](int value) -> bool {
        // Check if value satisfies the condition
        return true;
    };
    
    int left = minPossible, right = maxPossible;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (feasible(mid)) {
            result = mid;
            // Search for better answer
            right = mid - 1;  // or left = mid + 1
        } else {
            left = mid + 1;   // or right = mid - 1
        }
    }
    
    return result;
}

// Find leftmost/rightmost boundary
int findBoundary(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            result = mid;
            right = mid - 1;  // Continue searching left
            // Use left = mid + 1 for rightmost
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}