Binary Search

Binary Search is not only for sorted arrays. It applies whenever a decision splits the search space into "impossible on one side" and "still possible on the other side." The most important habit is defining the search interval and the predicate before coding.

Quick Identifier

• Topic: binary-search
• Pattern: Vanilla search, lower bound, rotated search, partition search, or search on answer.
• Core Question: Is there a monotonic rule that lets one comparison discard half the candidates?

Quick Sights

• Typical Time Complexity: O(log n) for direct search, or O(n log range) for search-on-answer feasibility checks.
• Typical Space Complexity: O(1).
• Core Mechanism: Maintain a valid search interval, test the midpoint, and shrink toward the side that can still contain the answer.

Diagram

Recognition Cues

• Sorted input with O(log n) expected.
• "Minimum capacity/speed/value such that...".
• Rotated sorted arrays, timestamps, peak/slope, or partitioned arrays.

Problem List

Start with 704. Binary Search, then 035. Search Insert Position, 074. Search a 2D Matrix, 033. Search in Rotated Sorted Array, and search-on-answer problems like 875. Koko Eating Bananas.