Binary Search Pattern

Binary Search is an efficient divide-and-conquer algorithm used to find a target value within a sorted collection or monotonic answer space. Instead of scanning elements one by one, Binary Search continually queries the middle element and discards half of the search space based on the comparison. This turns a linear $O(N)$ traversal into a logarithmic $O(log N)$ search.

By halving the problem size at each step, Binary Search can search a collection of 1 million elements in just 20 comparisons.

---

The Core Concept: Finding a Target in a Sorted Array

To understand this concept deeply, let's explore Binary Search.

Problem Statement: Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

Naive Brute Force — $O(N)$

A naive solution performs a linear search, checking every element from left to right:

While this is straightforward, it does not exploit the sorted nature of the array, requiring up to $O(N)$ steps.

The Binary Search Breakthrough — $O(log N)$

Since the array is sorted, we can use two pointers, low = 0 and high = len(nums) - 1. In each step, we calculate the middle index mid = low + (high - low) // 2:

• If the middle value matches the target, we return mid.
• If the middle value is less than the target, then because the array is sorted, the target must lie to the right of mid. We narrow our search space by setting low = mid + 1.
• If the middle value is greater than the target, the target must lie to the left of mid. We narrow our search space by setting high = mid - 1.

This decision rule eliminates half of the remaining elements at each step.

---

Step-by-Step Traversal

Let's trace the algorithm on the sorted array: [1, 3, 5, 8, 12, 15, 21, 28, 32, 45] with target 21.

Step 1: Initialization

We place the low pointer at index 0 and the high pointer at index 9.

Step 2: First Guess

• We calculate the midpoint: mid = (0 + 9) // 2 = 4 (value 12).

• We compare 12 with the target 21. Since $12 < 21$, the target must be in the right half.
• We discard the left half by moving low to mid + 1, which is index 5.

Step 3: Second Guess

• The active window is now indices 5 to 9.
• We calculate the midpoint: mid = (5 + 9) // 2 = 7 (value 28).

• We compare 28 with target 21. Since $28 > 21$, the target must be in the left half.
• We discard the right half by moving high to mid - 1, which is index 6.

Step 4: Third Guess

• The active window is now indices 5 to 6.
• We calculate the midpoint: mid = (5 + 6) // 2 = 5 (value 15).

• We compare 15 with target 21. Since $15 < 21$, the target must be in the right half.
• We move low to mid + 1, which is index 6.

Step 5: Solution Found

• The active window is now index 6 to 6 (both low and high point to index 6).
• We calculate the midpoint: mid = (6 + 6) // 2 = 6 (value 21).

• Since the value at index 6 matches the target (21 == 21), we return the index 6.

---

Code Implementation

Time Complexity: $O(log N)$ — the search space is divided by 2 in each iteration. Space Complexity: $O(1)$ — we only store a few pointer variables.

---

Core Variations

1. Searching Left/Right Boundaries

When duplicates exist in the sorted array, binary search can be customized to find the first (leftmost) or last (rightmost) index of a target.

• Approach: Instead of returning immediately when nums[mid] == target, keep narrowing the search window in that direction (setting high = mid for leftmost, or low = mid + 1 for rightmost).
• Example: Find First and Last Position of Element in Sorted Array.

2. Binary Search on Answer Space (Monotonic Feasibility)

The most powerful extension. Instead of searching a sorted array, search a range of integers representing possible answers (e.g., speed, capacity, time). A helper function is_feasible(x) checks if value $x$ is valid. Since the feasibility is monotonic (e.g., if speed $X$ works, all speeds $> X$ also work), we search the optimal threshold in $O(log( ext{range}) cdot ext{CostOfCheck})$.

• Examples: Koko Eating Bananas, Split Array Largest Sum, Minimum Shipping Capacity.

3. Search in Rotated Sorted Array

A sorted array that has been rotated at a pivot point (e.g., [4,5,6,7,0,1,2]).

• Approach: At any mid point, at least one half of the array (left or right) is guaranteed to be normally sorted. Check which half is sorted, and use boundaries to decide where to recurse.
• Example: Search in Rotated Sorted Array.

---

When Do I Use This?

Check for these conditions:

1. Is the input collection sorted, or can it be sorted without affecting requirements?
2. Are you searching for a specific value, pivot, or insertion index in linear time but need it faster?
3. Is the problem asking to find a minimum or maximum answer under a certain constraint, where validity follows a "pass/fail" partition?

If yes, you should apply Binary Search.

---

Practice Problems