Binary Search Pattern

The Binary Search pattern is a range reduction technique that locates a target value within a sorted collection by comparing the target against the middle element and discarding half of the remaining search space on each step.

Recognition Signals

You should consider this pattern if you see any of the following cues in the problem description:

• The input array is sorted.
• You need to search for a target value or boundary point in better than O(n) linear time.
• The target time complexity is explicitly specified as O(log n).
• The problem asks to find the minimum or maximum value of a condition that is monotonic (e.g. if speed S works, any speed > S also works, and if speed S fails, any speed < S also fails).

How It Works

Instead of checking elements one by one (O(n)), you track the range boundaries using left and right indices. At each step:

• Compute the middle index: mid = left + (right - left) / 2.
• Compare the element at mid to the target.
• If it matches, return the index.
• If nums[mid] < target, the target must be in the right half, so you set left = mid + 1.
• If nums[mid] > target, the target must be in the left half, so you set right = mid - 1.

For example, to find 7 in [1, 3, 5, 7, 9]:

1. Initialize: left = 0, right = 4.
2. Step 1: mid = 2 (val 5). Since 5 < 7, shift left = mid + 1 = 3.
3. Step 2: mid = 3 (val 7). Match found. Return index 3.

Complexity, With Caveats

• Time Complexity: O(log n) where n is the number of elements in the range. The search space is divided by 2 at each step.
• Space Complexity: O(1) auxiliary space when implemented iteratively, as it only uses three tracking variables.

Minimal Code Template

public class BinarySearchTemplate {
    // Standard Binary Search
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            // prevent integer overflow compared to (left + right) / 2
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid; // match found
            } else if (nums[mid] < target) {
                left = mid + 1; // search right half
            } else {
                right = mid - 1; // search left half
            }
        }
        return -1; // target not found
    }
}

# Standard Binary Search
def search(nums: list[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

    while left <= right:
        # prevent integer overflow
        mid = left + (right - left) // 2

        if nums[mid] == target:
            # match found
            return mid
        elif nums[mid] < target:
            # search right half
            left = mid + 1
        else:
            # search left half
            right = mid - 1

    return -1  # target not found

#include <vector>

class BinarySearchTemplate {
public:
    // Standard Binary Search
    int search(const std::vector<int>& nums, int target) {
        int left = 0;
        int right = (int)nums.size() - 1;

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

            if (nums[mid] == target) {
                return mid; // match found
            } else if (nums[mid] < target) {
                left = mid + 1; // search right half
            } else {
                right = mid - 1; // search left half
            }
        }
        return -1; // target not found
    }
};

Where This Pattern Falls Short

• Unsorted arrays: If the array is not sorted, binary search cannot be applied. Sorting first takes O(n log n) time, which is slower than a simple O(n) linear search if you only perform a single query.
• Linked Lists: Binary search relies on O(1) random access to find the middle element. In a linked list, finding the middle element takes O(n) steps, reducing binary search to O(n log n) time, which is slower than a simple O(n) linear scan.

Related Patterns, Compared

• Two Pointers: choose this instead when you need to find pairs of elements or modify values in-place rather than searching for a single target or boundary.
• Binary Search on Answer: choose this when the array itself is not sorted, but the output condition is monotonic, allowing you to binary search the values of the possible results instead of array indices.

Frequently Asked Questions

Why do we write left + (right - left) / 2 instead of (left + right) / 2? If left and right are very large, adding them together can exceed the maximum bounds of a 32-bit signed integer, causing overflow errors. Subtracting them first prevents this.

Can binary search find elements in rotated arrays? Yes. You can adapt the algorithm by checking which half of the array is sorted at the current mid index, and then determining if the target falls within that sorted half.

What does this pattern test in interviews? It tests your comfort with boundary conditions, loop termination rules, and avoiding integer overflows.