Shrinking the Search Space with Binary Search

type

status

date

summary

Core Idea

At its heart, Binary Search is fundamentally a divide-and-conquer algorithm:

Start with the entire search space.

Check the middle element (or midpoint condition).

Decide whether to continue searching in the left half or the right half.

Repeat until the search space collapses to the answer or becomes empty.

This recursive halving guarantees logarithmic performance, making Binary Search a cornerstone of efficient algorithm design.

Common Usages of Binary Search

Binary Search appears in many algorithmic patterns and real-world systems. Below are the most common use cases.

1. Value Lookup and Existence Check

This is the classic template for checking if a target exists and returning its index.

It uses a closed interval [left, right] and narrows the space until the pointers meet.

2. Boundary and Insertion Point Searches

These templates are used to find the correct insertion index for an element, even if the element doesn't exist. They use a half-open interval approach (left < right) where the result is always left.

Pattern Name	Goal	Condition to Advance left	Result after loop
Lower Bound	Find the first occurrence of `≥ target` (Smallest index greater than or equal to target).	`sorted_list[mid] < target`	`left` is the insertion index.
Upper Bound	Find the position after the last occurrence of `<= target` (Smallest index strictly greater than target).	`sorted_list[mid] <= target`	`left` is the index after the target's group.

Template —Lower Bound

Template —Upper Bound

3. Finding the Closest Element

To find the closest element to a target value, combine a lower bound search with a small post-processing step comparing neighbors.

Use Case: Nearest temperature, closest stock price, or minimizing |nums[i] − target|.

4. Binary Search on the Answer

This is a meta-technique where you binary search not over indices, but over possible answers.

This pattern appears in scheduling, optimization, and many “minimize the maximum” problems.

Template — Minimize Feasible Value

Example: Koko Eating Bananas (LeetCode 875)

Find the minimum eating speed k so Koko can finish all piles within h hours.

Monotonic property: If Koko can finish with speed = k, she can also finish with any speed > k.

Common Pitfalls

Infinite loops:

Always ensure the range shrinks (left < right → left = mid + 1 or right = mid).

Off-by-one errors:

Closed vs. half-open intervals produce different exit conditions.

Integer overflow (in lower-level languages):

Use mid = left + (right - left)//2 instead of (left + right)//2 to avoid integer overflow.

Binary Search Variants in the Wild

Binary search is not just simple number lookups — it’s a pattern that adapts to many complex problem types once you recognize the underlying monotonic behavior.

Once you see that your “search condition” behaves monotonically, even if the data looks nonlinear or multidimensional, you can usually model it as a binary search on some ordered feature — index, value, or even decision space.

Problem	Binary Search Target	Example
Rotated Sorted Array	Search in rotated array using pivot logic	LeetCode 33
Peak Element	Find local maximum using slope property	LeetCode 162
Minimum in Rotated Array	Find min value via monotonic segments	LeetCode 153
Allocate Books / Split Array	Minimize largest partition sum	LeetCode 410
Matrix Search	Binary search over 2D matrix or flattened index	LeetCode 74
Search in a Sorted Array of Unknown Size	Determine search bounds first (exponential expansion), then apply binary search within them	LeetCode 702

Final Thought

By repeatedly dividing the search space in half and narrowing down where the target might be, binary search achieves a time complexity of O(log⁡n), making it vastly faster than linear search for large datasets. Its efficiency, simplicity, and predictability make it a critical building block in many algorithms and real-world applications.