Binary Search Pattern¶

Overview¶

Divide search space in half repeatedly to find target or boundary in O(log n) time. Works on sorted arrays and monotonic functions.

When to Use¶

Searching in sorted array
Finding boundary (first/last occurrence)
Searching in rotated sorted array
Search in matrix
Minimize/maximize problems with monotonic property
Finding square root, peak element

Key Insight: Each step eliminates half the remaining elements, giving O(log n) time complexity.

Template Code¶

Standard Binary Search¶

public int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;  // Avoid overflow

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;  // Not found
}

Find First Occurrence (Lower Bound)¶

public int findFirst(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    int result = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            result = mid;
            right = mid - 1;  // Keep searching left
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return result;
}

Find Last Occurrence (Upper Bound)¶

public int findLast(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    int result = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            result = mid;
            left = mid + 1;  // Keep searching right
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return result;
}

Search in Rotated Sorted Array¶

public int searchRotated(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid;
        }

        // Determine which half is sorted
        if (nums[left] <= nums[mid]) {
            // Left half is sorted
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // Right half is sorted
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    return -1;
}

Find Minimum in Rotated Sorted Array¶

public int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] > nums[right]) {
            left = mid + 1;  // Min is in right half
        } else {
            right = mid;  // Min could be mid or left
        }
    }

    return nums[left];
}

// With duplicates
public int findMinWithDuplicates(int[] nums) {
    int left = 0, right = nums.length - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else if (nums[mid] < nums[right]) {
            right = mid;
        } else {
            right--;  // Handle duplicates
        }
    }

    return nums[left];
}

Find Peak Element¶

public int findPeakElement(int[] nums) {
    int left = 0, right = nums.length - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] > nums[mid + 1]) {
            right = mid;  // Peak is on left (including mid)
        } else {
            left = mid + 1;  // Peak is on right
        }
    }

    return left;
}

Search a 2D Matrix¶

// Matrix where each row is sorted and first element > last of prev row
public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    int left = 0, right = m * n - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        int value = matrix[mid / n][mid % n];

        if (value == target) {
            return true;
        } else if (value < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return false;
}

// Matrix where rows and columns are sorted independently
public boolean searchMatrixII(int[][] matrix, int target) {
    int row = 0, col = matrix[0].length - 1;

    while (row < matrix.length && col >= 0) {
        if (matrix[row][col] == target) {
            return true;
        } else if (matrix[row][col] > target) {
            col--;
        } else {
            row++;
        }
    }

    return false;
}

Sqrt(x) - Integer Square Root¶

public int mySqrt(int x) {
    if (x < 2) return x;

    long left = 1, right = x / 2;

    while (left <= right) {
        long mid = left + (right - left) / 2;
        long square = mid * mid;

        if (square == x) {
            return (int) mid;
        } else if (square < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return (int) right;  // Floor of sqrt
}

Koko Eating Bananas (Min Speed)¶

public int minEatingSpeed(int[] piles, int h) {
    int left = 1;
    int right = Arrays.stream(piles).max().getAsInt();

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (canFinish(piles, h, mid)) {
            right = mid;  // Try smaller speed
        } else {
            left = mid + 1;
        }
    }

    return left;
}

private boolean canFinish(int[] piles, int h, int speed) {
    int hours = 0;
    for (int pile : piles) {
        hours += (pile + speed - 1) / speed;  // Ceiling division
    }
    return hours <= h;
}

Capacity to Ship Packages¶

public int shipWithinDays(int[] weights, int days) {
    int left = Arrays.stream(weights).max().getAsInt();
    int right = Arrays.stream(weights).sum();

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (canShip(weights, days, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

private boolean canShip(int[] weights, int days, int capacity) {
    int daysNeeded = 1, currentLoad = 0;

    for (int weight : weights) {
        if (currentLoad + weight > capacity) {
            daysNeeded++;
            currentLoad = 0;
        }
        currentLoad += weight;
    }

    return daysNeeded <= days;
}

Time & Space Complexity¶

Problem	Time	Space
Standard search	O(log n)	O(1)
First/last occurrence	O(log n)	O(1)
Rotated array	O(log n)	O(1)
Find min rotated	O(log n)	O(1)
Peak element	O(log n)	O(1)
2D matrix	O(log(mn))	O(1)
Sqrt(x)	O(log x)	O(1)

Common Interview Questions¶

Binary Search - Basic search in sorted array
Search Insert Position - Where to insert if not found
First and Last Position - Range of target
Search in Rotated Sorted Array - With/without duplicates
Find Minimum in Rotated Array - With/without duplicates
Find Peak Element - Local maximum
Search a 2D Matrix - Both variants
Sqrt(x) - Integer square root
Guess Number Higher or Lower - Classic binary search
Koko Eating Bananas - Minimize speed
Capacity to Ship Packages - Minimize capacity
Split Array Largest Sum - Minimize largest sum
Median of Two Sorted Arrays - Hard classic
Find K Closest Elements - Binary search + two pointers

Tips & Tricks¶

Use left + (right - left) / 2 to avoid integer overflow
left <= right for finding exact target
left < right for finding boundary
For minimizing: if condition met, right = mid; else left = mid + 1
For maximizing: if condition met, left = mid; else right = mid - 1
For rotated arrays: identify which half is sorted first
Binary search on answer space when optimizing monotonic functions