Binary Search Technique
High ImportanceSystematically halve monotonic search spaces at every step to locate target values or determine optimal feasibility boundaries in logarithmic O(log N) time instead of O(N) linear scan.
When to Use Binary Search:
Key problem characteristics and signals indicating that this technique is the optimal choice.
Searching for an exact target value or determining existence in a sorted array or sequence.
Locating first or last occurrence (Lower Bound / Upper Bound / Insertion Index) in a sorted array with duplicates.
Rotated sorted array searches where at least one half is guaranteed to remain strictly sorted.
Binary Search on Answer: finding the minimum or maximum feasible integer threshold satisfying a monotonic predicate.
Finding peak elements in unsorted or bitonic arrays where slope direction arr[mid] < arr[mid + 1] guides the search.
Prerequisite Rule: Monotonicity Invariant: Binary search does not strictly require the array to be sorted, but it mathematically requires the decision predicate P(x) to be monotonic (false...false...true...true or true...true...false...false). If evaluating mid does not definitively eliminate at least one entire half of the search space, standard binary search cannot be applied.
Example Problem — Search in a Sorted Array
The benchmark interview problem demonstrating the transition from quadratic brute force to linear optimality.
Problem Statement
Given a sorted array of distinct integers arr[] and an integer target, return the index of target if it exists in the array. If target does not exist, return -1.
arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], target = 23
5 (arr[5] == 23)
Explanation: Element 23 is located at index 5. In binary search, we evaluate mid: arr[4]=16 < 23 -> discard left half; arr[7]=56 > 23 -> discard right half; arr[5]=23 == 23 -> match found in only 3 comparisons instead of 6 linear checks!
Naive Method (Linear Scan) — O(n) Time and O(1) Space
The baseline brute force approach recalculating candidates through nested loops.
The naive approach iterates through the array from index 0 to n - 1, checking each element one by one until target is found or the array ends.
def binary_search_naive(arr: list[int], target: int) -> int: # Linear scan through each element for i in range(len(arr)): if arr[i] == target: return i # Found target at index i return -1 # Not foundWhy Naive Fails in Production & Interviews
For an array with n = 10⁹ elements or 10⁵ repeated queries on n = 10⁵ elements, linear search takes 10¹⁰ operations and causes Time Limit Exceeded (TLE). It is completely blind to sorted order, discarding zero information from prior comparisons.
Binary Search Technique — O(log n) Time and O(1) Space
The optimal strategy leveraging binary search mechanics to achieve optimal time complexity.
Maintain low and high pointers enclosing the active search space. Compare the middle element arr[mid] to target. Because the array is sorted, this single comparison discards half of the entire remaining elements in O(1) time.
1. Initialize Boundary Pointers: Set low = 0 and high = n - 1, enclosing the entire sorted array.
2. Compute Middle Index Safely: Calculate mid = low + (high - low) // 2 to avoid 32-bit integer overflow.
3. Evaluate Match (arr[mid] == target): If arr[mid] matches target, return mid immediately. Target found in O(1) comparisons.
4. Target is Greater (arr[mid] < target): Because array is sorted, all elements at or before mid are strictly smaller than target. Discard left half: set low = mid + 1.
5. Target is Smaller (arr[mid] > target): Because array is sorted, all elements at or after mid are strictly larger than target. Discard right half: set high = mid - 1.
Interactive Trace
Interactive Trace: Binary Search (arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], Target = 23)
Interactive Trace: Binary Search (arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], Target = 23)
arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], target = 23
Index 5 (arr[5] == 23)
State Mutation Inspector
Decision & Invariant Action
Active range [0..9]. Midpoint = 0 + (9-0)//2 = 4 (val 16). Since 16 < 23 and array is sorted, target cannot be in [0..4]. Advance low to 5.
Binary Search Algorithm Code
Complete runnable solution in Python, C++, Java, and JavaScript.
def binary_search(arr: list[int], target: int) -> int: """ Standard Binary Search Template Time Complexity: O(log N) | Space Complexity: O(1) """ low, high = 0, len(arr) - 1 while low <= high: mid = low + (high - low) // 2 if arr[mid] == target: return mid elif arr[mid] < target: low = mid + 1 else: high = mid - 1 return -1How does this work?
Logarithmic Space Halving & The Overflow-Safe Midpoint Invariant
Each comparison eliminates half of the remaining elements. A search space of size N reduces to N/2, N/4, ..., 1 in at most ceil(log2 N) steps. For 1,000,000,000 elements, Binary Search takes at most 30 comparisons.
1. Exponential Space Reduction Invariant
If arr[mid] < target, then because the array is sorted in ascending order, arr[i] <= arr[mid] < target for all i <= mid. None of the indices 0 ... mid can possibly contain target. Eliminating them is 100% mathematically safe and shrinks the candidate space by exactly 50% in O(1).
2. Master Theorem Logarithmic Recurrence Proof
The recurrence relation is T(N) = T(N / 2) + O(1). Solving via Master Theorem yields T(N) = O(log2 N). For N = 10^5, at most ~17 comparisons are executed; for N = 10^9, at most ~30 comparisons; for N = 10^18, at most ~60 comparisons.
3. The Overflow-Safe Midpoint Invariant
Computing mid = (low + high) / 2 can overflow signed 32-bit integers when low + high > 2^31 - 1, producing a negative index. The mathematically equivalent mid = low + (high - low) / 2 strictly guarantees that no intermediate calculation exceeds high, preventing overflow bugs forever.
4. Boundary Condition Correctness (low <= high)
When low == high, exactly 1 element remains to be inspected. Using while (low <= high) guarantees that this final single-element candidate is evaluated before terminating, ensuring zero false negatives.
Core Pattern Variations & Blueprints
Explore the 3 structural variations that power all binary search interview problems. Click each variation to expand its blueprint, interactive dry run, and implementation.
Find the earliest element >= target (lower bound) or first element > target (upper bound) in sorted arrays containing duplicate values. Instead of halting on arr[mid] == target, continue searching the left half to record the boundary.
The Algorithmic Invariant
When arr[mid] >= target, record candidate index ans = mid, then contract high = mid - 1 to search for earlier instances.
Pointer Traversal Flow
Array with Duplicates: [ 2, 4, 8, 8, 8, 12, 16 ]
Target = 8
First Occurrence (Lower Bound) ──► Index 2
Last Occurrence ──► Index 4Worked Example: Find First Occurrence of Target 8 (arr = [2, 4, 8, 8, 8, 12, 16])
arr = [2, 4, 8, 8, 8, 12, 16], target = 8Step 1: low=0, high=6 -> mid=3 (val 8). 8 == 8! Record ans = 3. Search left: high = mid - 1 = 2.
Step 2: low=0, high=2 -> mid=1 (val 4). 4 < 8. Search right: low = mid + 1 = 2.
Step 3: low=2, high=2 -> mid=2 (val 8). 8 == 8! Record ans = 2. Search left: high = 1.
Step 4: low=2 > high=1 -> Loop terminates. Return earliest index = 2.
Interactive Dry Run Simulator
Boundary Trace: First Occurrence of Target 8
arr = [2, 4, 8, 8, 8, 12, 16], target = 8
First Occurrence Index = 2
State Mutation Inspector
Decision & Invariant Action
mid=3 has value 8. Record candidate ans=3. Since we want first occurrence, search left half: high = 2.
Production-Grade Implementation
def lower_bound(arr: list[int], target: int) -> int: """ Find first occurrence index of target (or insertion index) Time Complexity: O(log N) | Space Complexity: O(1) """ low, high = 0, len(arr) - 1 ans = -1 while low <= high: mid = low + (high - low) // 2 if arr[mid] == target: ans = mid high = mid - 1 # Keep exploring left half elif arr[mid] < target: low = mid + 1 else: high = mid - 1 return ansLandmine to Avoid: Halting immediately when arr[mid] == target, which returns an arbitrary occurrence rather than the strictly first or last boundary index.
Curated Practice Ladder
Master this pattern progressively through verified interview questions.
Create a free account to track progress and unlock your free practice set.
Premium also includes the full problem library, detailed solutions, hints, and advanced revision tools.
Already have an account? Log in
“Master the invariants,
and the solution
writes itself.”
