--- # === IDENTITY === id: software/patterns/binary-search-variations/2026 canonical_question: "What are the common binary search variations and patterns?" aliases: - "binary search lower bound upper bound" - "how to implement binary search correctly" - "binary search on answer space pattern" - "rotated array binary search template" - "binary search off-by-one errors" - "generalized binary search monotonic function" entity_type: software_reference domain: software > patterns > binary_search_variations region: global jurisdiction: global temporal_scope: 2020-2026 # === VERIFICATION === last_verified: 2026-02-24 confidence: 0.95 version: 1.0 first_published: 2026-02-24 # === TEMPORAL VALIDITY === temporal_validity: status: stable last_breaking_change: null next_review: 2026-08-23 change_sensitivity: low # === CONSTRAINTS === constraints: - "Array or search space MUST exhibit monotonic property (sorted, or predicate transitions from false to true) for binary search to be correct" - "Always compute mid as lo + (hi - lo) / 2 (or lo + (hi - lo + 1) / 2 for upper variant) to prevent integer overflow in C++/Java" - "Never update both boundaries to mid without +1 or -1 adjustment — this causes infinite loops when hi - lo == 1" - "For rotated array search: determine which half is sorted FIRST, then decide if target falls in that half" # === SKIP CONDITIONS === skip_this_unit_if: - condition: "Need to search in an unsorted collection with no monotonic property" use_instead: "Hash table lookup O(1) or linear scan O(n)" - condition: "Need to find multiple matching elements, not just one boundary" use_instead: "Two binary searches (lower_bound + upper_bound) to find the range" - condition: "Search space is a graph or tree structure" use_instead: "BFS/DFS traversal or binary search tree operations" # === AGENT HINTS === inputs_needed: - key: search_type question: "What type of binary search do you need?" type: choice options: ["exact match", "lower bound (first >=)", "upper bound (first >)", "rotated array", "search on answer space", "peak element", "matrix search"] # === DISTRIBUTION === canonical_source: "https://knowledgelib.io/software/patterns/binary-search-variations/2026" suggested_citation: "Source: knowledgelib.io — AI Knowledge Library (verified 2026-02-24)" # === RELATED UNITS === related_kos: related_to: - id: software/patterns/sorting-algorithms/2026 label: "Sorting Algorithms" - id: software/patterns/two-pointer-technique/2026 label: "Two Pointer Technique" - id: software/patterns/dynamic-programming/2026 label: "Dynamic Programming" solves: - id: software/patterns/search-in-rotated-array/2026 label: "Search in Rotated Array" often_confused_with: - id: software/patterns/ternary-search/2026 label: "Ternary Search (for unimodal functions, not monotonic)" # === SOURCES (7 authoritative sources) === sources: - id: src1 title: "Binary Search — Algorithms for Competitive Programming" author: CP-Algorithms url: https://cp-algorithms.com/num_methods/binary_search.html type: community_resource published: 2024-06-15 reliability: high - id: src2 title: "An Opinionated Guide to Binary Search" author: LeetCode Community url: https://leetcode.com/discuss/post/2371234/an-opinionated-guide-to-binary-search-co-1yfw/ type: community_resource published: 2024-01-10 reliability: high - id: src3 title: "The Curious Case of Binary Search — The Famous Bug That Remained Undetected for 20 Years" author: Mohit Chawla url: https://thebittheories.com/the-curious-case-of-binary-search-the-famous-bug-that-remained-undetected-for-20-years-973e89fc212 type: technical_blog published: 2023-08-12 reliability: moderate_high - id: src4 title: "Binary Search — USACO Guide" author: USACO Guide url: https://usaco.guide/silver/binary-search type: community_resource published: 2024-03-01 reliability: high - id: src5 title: "Binary Search for Beginners — Problems, Patterns, Sample Solutions" author: LeetCode Community url: https://leetcode.com/discuss/general-discussion/691825/Binary-Search-for-Beginners-Problems-or-Patterns-or-Sample-solutions type: community_resource published: 2023-05-20 reliability: high - id: src6 title: "Binary Search Patterns That Solve 80% of LeetCode Problems" author: LeetCode Community url: https://leetcode.com/discuss/post/7441588/binary-search-patterns-that-solve-80-of-qu83f/ type: community_resource published: 2025-01-15 reliability: moderate_high - id: src7 title: "TopCoder — Binary Search Tutorial" author: TopCoder url: https://www.topcoder.com/community/competitive-programming/tutorials/binary-search type: community_resource published: 2022-09-01 reliability: high --- # Binary Search Variations: Complete Reference ## TL;DR - **Bottom line**: Binary search applies far beyond sorted arrays — use it on any monotonic predicate (a function that transitions from false to true or vice versa) to find the boundary in O(log n) time. - **Key tool**: `lo`/`hi` pointers with strict invariant maintenance — always ensure the search space shrinks by at least 1 each iteration. - **Watch out for**: Off-by-one errors in boundary updates and integer overflow in mid calculation (`(lo + hi) / 2` overflows in Java/C++ for large values — use `lo + (hi - lo) / 2` instead). [src3] - **Works with**: Any language, any sorted/monotonic search space. Patterns are language-agnostic. ## Constraints - The search space MUST be monotonic: either the array is sorted, or a boolean predicate transitions from all-false to all-true (or vice versa). Binary search on non-monotonic data produces incorrect results silently. - Always use overflow-safe mid calculation: `mid = lo + (hi - lo) / 2`. The expression `(lo + hi) / 2` caused a bug in Java's `Arrays.binarySearch` that went undetected for 20 years. [src3] - When using `while (lo < hi)` with `lo = mid` (not `mid + 1`), you MUST use `mid = lo + (hi - lo + 1) / 2` (ceiling division) to prevent infinite loops. - For rotated array problems, always determine which half is sorted before deciding where the target lies. Comparing `arr[lo]` vs `arr[mid]` tells you which half is sorted. ## Quick Reference | Variation | Template Pattern | Time | Space | Key Insight | |---|---|---|---|---| | Standard (exact match) | `while lo <= hi`, return on match | O(log n) | O(1) | Classic — search terminates on exact match or empty range | | Lower bound (first >=) | `while lo < hi`, `hi = mid` | O(log n) | O(1) | Finds leftmost insertion point; equivalent to C++ `lower_bound` | | Upper bound (first >) | `while lo < hi`, `lo = mid + 1` | O(log n) | O(1) | Finds rightmost insertion point; equivalent to C++ `upper_bound` | | First true (generalized) | `while lo < hi`, predicate check | O(log n * T(f)) | O(1) | Works on any monotonic predicate, not just arrays [src1] | | Rotated array minimum | `while lo < hi`, compare `mid` vs `hi` | O(log n) | O(1) | Compare with rightmost element, not leftmost — handles duplicates edge case | | Rotated array search | `while lo <= hi`, check sorted half | O(log n) | O(1) | Identify sorted half first, then check if target is within it | | Peak element | `while lo < hi`, compare `mid` vs `mid+1` | O(log n) | O(1) | Move toward the ascending side; works on any bitonic sequence | | Search on answer | `while lo < hi`, feasibility check | O(log R * T(check)) | O(1) | Binary search the answer, not the array — verify feasibility [src4] | | Matrix search (sorted rows+cols) | Treat as 1D, or row-then-col | O(log(m*n)) | O(1) | Flatten 2D index: `row = mid / cols`, `col = mid % cols` | | Leftmost / rightmost match | Two passes: lower_bound + upper_bound | O(log n) | O(1) | Combine to find count of target: `upper - lower` | ## Decision Tree > Full script: [decision-tree.txt](scripts/decision-tree.txt) (28 lines) ``` START ├── Is the search space a sorted array? │ ├── YES → Need exact match? │ │ ├── YES → Standard binary search (while lo <= hi) │ │ └── NO → Need first element >= target? # ... (see full script) ``` ## Step-by-Step Guide ### 1. Implement the standard binary search template The foundation of all variations. Use `while lo <= hi` for exact match, return immediately when found. [src1] ```python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 if arr[mid] == target: return mid # found elif arr[mid] < target: lo = mid + 1 # target is in right half else: hi = mid - 1 # target is in left half return -1 # not found ``` **Verify**: `binary_search([1, 3, 5, 7, 9], 5)` -> expected output: `2` ### 2. Implement lower bound (first element >= target) Used for finding insertion points, counting elements, and range queries. The key difference: never return early, always narrow to convergence. [src2] ```python def lower_bound(arr, target): lo, hi = 0, len(arr) # hi = len(arr), NOT len(arr)-1 while lo < hi: # strict <, NOT <= mid = lo + (hi - lo) // 2 if arr[mid] < target: lo = mid + 1 # arr[mid] is too small else: hi = mid # arr[mid] >= target, could be answer return lo # lo == hi == first index >= target ``` **Verify**: `lower_bound([1, 3, 5, 5, 7], 5)` -> expected output: `2` (first index where value >= 5) ### 3. Implement upper bound (first element > target) Combined with lower bound, gives you the range `[lower_bound, upper_bound)` containing all copies of target. [src2] ```python def upper_bound(arr, target): lo, hi = 0, len(arr) while lo < hi: mid = lo + (hi - lo) // 2 if arr[mid] <= target: # only difference: <= instead of < lo = mid + 1 else: hi = mid return lo # first index > target ``` **Verify**: `upper_bound([1, 3, 5, 5, 7], 5)` -> expected output: `4` (first index where value > 5) ### 4. Implement search in rotated sorted array Determine which half is sorted by comparing `arr[lo]` vs `arr[mid]`, then check if target lies in the sorted half. [src6] ```python def search_rotated(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 if arr[mid] == target: return mid # Left half is sorted if arr[lo] <= arr[mid]: if arr[lo] <= target < arr[mid]: hi = mid - 1 # target in sorted left half else: lo = mid + 1 # target in right half # Right half is sorted else: if arr[mid] < target <= arr[hi]: lo = mid + 1 # target in sorted right half else: hi = mid - 1 # target in left half return -1 ``` **Verify**: `search_rotated([4, 5, 6, 7, 0, 1, 2], 0)` -> expected output: `4` ### 5. Implement search on answer space When you cannot directly find the answer but can verify if a candidate works, binary search the answer itself. Define a feasibility predicate and binary search until convergence. [src4] ```python def search_on_answer(lo, hi, is_feasible): """Find the minimum value in [lo, hi] where is_feasible returns True. Precondition: is_feasible is monotonic (False...False, True...True).""" while lo < hi: mid = lo + (hi - lo) // 2 if is_feasible(mid): hi = mid # mid works, try smaller else: lo = mid + 1 # mid doesn't work, need larger return lo # smallest feasible answer ``` **Verify**: `search_on_answer(1, 100, lambda x: x * x >= 50)` -> expected output: `8` (since 8*8=64 >= 50, but 7*7=49 < 50) ### 6. Implement peak element finder For bitonic arrays (increase then decrease), compare `arr[mid]` with `arr[mid+1]` to decide direction. [src5] ```python def find_peak(arr): lo, hi = 0, len(arr) - 1 while lo < hi: mid = lo + (hi - lo) // 2 if arr[mid] < arr[mid + 1]: lo = mid + 1 # peak is to the right else: hi = mid # peak is at mid or to the left return lo # lo == hi == peak index ``` **Verify**: `find_peak([1, 3, 7, 5, 2])` -> expected output: `2` (index of peak value 7) ## Code Examples ### Python: Complete binary search toolkit ```python # Input: sorted array and target value # Output: index or insertion point depending on function from bisect import bisect_left, bisect_right # Python's standard library already provides lower/upper bound: # bisect_left = lower_bound (first index >= target) # bisect_right = upper_bound (first index > target) arr = [1, 3, 5, 5, 5, 7, 9] target = 5 first_occurrence = bisect_left(arr, target) # 2 last_occurrence = bisect_right(arr, target) - 1 # 4 count = bisect_right(arr, target) - bisect_left(arr, target) # 3 ``` ### JavaScript: Lower bound and search on answer ```javascript // Input: sorted array, target value // Output: index of first element >= target function lowerBound(arr, target) { let lo = 0, hi = arr.length; while (lo < hi) { const mid = lo + ((hi - lo) >> 1); // bit shift = floor division by 2 if (arr[mid] < target) lo = mid + 1; else hi = mid; } return lo; } // Search on answer: find minimum capacity to ship within D days function shipWithinDays(weights, days) { let lo = Math.max(...weights); let hi = weights.reduce((a, b) => a + b, 0); while (lo < hi) { const mid = lo + ((hi - lo) >> 1); if (canShip(weights, days, mid)) hi = mid; else lo = mid + 1; } return lo; } ``` ### Java: Overflow-safe binary search ```java // Input: sorted int array, target // Output: index of target, or -1 public static int binarySearch(int[] arr, int target) { int lo = 0, hi = arr.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // overflow-safe if (arr[mid] == target) return mid; else if (arr[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1; } // Rotated array: find minimum element public static int findMin(int[] arr) { int lo = 0, hi = arr.length - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] > arr[hi]) lo = mid + 1; // min in right half else hi = mid; // min in left half (incl. mid) } return arr[lo]; } ``` ### C++: Using STL and custom predicates ```cpp // Input: sorted vector, target value // Output: iterator to first element >= target #include #include // STL provides lower_bound and upper_bound directly: std::vector v = {1, 3, 5, 5, 7, 9}; auto lb = std::lower_bound(v.begin(), v.end(), 5); // points to first 5 auto ub = std::upper_bound(v.begin(), v.end(), 5); // points to 7 int count = std::distance(lb, ub); // 2 copies of 5 // Custom predicate with partition_point (C++20-style): // Find smallest x in [1, 1000000] where x*x >= n auto it = std::partition_point( v.begin(), v.end(), [&](int x) { return (long long)x * x < n; } ); ``` ## Anti-Patterns ### Wrong: Integer overflow in mid calculation ```java // BAD — overflows when lo + hi > Integer.MAX_VALUE int mid = (lo + hi) / 2; ``` ### Correct: Overflow-safe mid calculation ```java // GOOD — subtraction cannot overflow when both are non-negative int mid = lo + (hi - lo) / 2; // Or in C++20: std::midpoint(lo, hi) ``` This bug existed in Java's `Arrays.binarySearch` for 9 years before being discovered in 2006. [src3] ### Wrong: Infinite loop with lo = mid ```python # BAD — when hi - lo == 1, mid == lo, and lo never advances while lo < hi: mid = lo + (hi - lo) // 2 # floor division if condition(mid): hi = mid else: lo = mid # INFINITE LOOP when hi == lo + 1 ``` ### Correct: Always shrink the search space ```python # GOOD — use mid + 1 for lo assignment, or ceiling division for mid while lo < hi: mid = lo + (hi - lo) // 2 if condition(mid): hi = mid else: lo = mid + 1 # guarantees progress ``` ### Wrong: Off-by-one in search boundaries ```python # BAD — misses the last element or goes out of bounds def lower_bound(arr, target): lo, hi = 0, len(arr) - 1 # hi should be len(arr) for lower_bound while lo < hi: mid = lo + (hi - lo) // 2 if arr[mid] < target: lo = mid + 1 else: hi = mid return lo # wrong when target > all elements ``` ### Correct: Use half-open interval [lo, hi) ```python # GOOD — hi = len(arr) handles "target greater than all" correctly def lower_bound(arr, target): lo, hi = 0, len(arr) # half-open interval [0, n) while lo < hi: mid = lo + (hi - lo) // 2 if arr[mid] < target: lo = mid + 1 else: hi = mid return lo # returns len(arr) if target > all elements ``` ### Wrong: Rotated array — comparing with wrong boundary ```python # BAD — comparing mid with lo doesn't handle all rotation cases def find_min_rotated(arr): lo, hi = 0, len(arr) - 1 while lo < hi: mid = lo + (hi - lo) // 2 if arr[mid] > arr[lo]: # wrong comparison lo = mid + 1 else: hi = mid return arr[lo] # fails on [2, 1] — returns 2, not 1 ``` ### Correct: Compare mid with hi for minimum finding ```python # GOOD — comparing with hi correctly identifies which half contains minimum def find_min_rotated(arr): lo, hi = 0, len(arr) - 1 while lo < hi: mid = lo + (hi - lo) // 2 if arr[mid] > arr[hi]: # min must be in right half lo = mid + 1 else: # min is in left half (including mid) hi = mid return arr[lo] # correctly returns 1 for [2, 1] ``` ## Common Pitfalls - **Integer overflow in mid calculation**: In Java/C++, `(lo + hi)` exceeds `Integer.MAX_VALUE` for large arrays. Fix: `mid = lo + (hi - lo) / 2`. This affected production code for decades. [src3] - **Wrong loop condition (< vs <=)**: Using `while lo < hi` when you need `while lo <= hi` (or vice versa) either misses the last candidate or causes infinite loops. Fix: Use `<=` for exact match (return inside loop), `<` for convergence (return after loop). [src2] - **Forgetting to handle empty results**: Lower bound on an empty array or with target larger than all elements returns `len(arr)` — not checking this causes index-out-of-bounds. Fix: Always check `if lo < len(arr) and arr[lo] == target` after binary search. [src5] - **Infinite loop from `lo = mid` with floor division**: When `hi = lo + 1`, `mid = lo + (hi - lo) // 2 = lo`, and setting `lo = mid` makes no progress. Fix: Either use `lo = mid + 1` or ceiling division `mid = lo + (hi - lo + 1) // 2`. [src1] - **Applying binary search to non-monotonic data**: Binary search only works on monotonic predicates. Applying it to unsorted data or non-monotonic functions silently returns wrong answers. Fix: Verify monotonicity before applying binary search. [src7] - **Duplicates in rotated array**: With duplicates, worst case degrades to O(n) because you cannot determine which half is sorted when `arr[lo] == arr[mid] == arr[hi]`. Fix: Skip duplicates with `lo++` or `hi--` when all three are equal. [src6] ## When to Use / When Not to Use | Use When | Don't Use When | Use Instead | |---|---|---| | Data is sorted or search space has a monotonic property | Data is unsorted with no ordering property | Hash table O(1) lookup or linear scan | | Need O(log n) search in a static sorted array | Array is frequently modified (many inserts/deletes) | Balanced BST (e.g., AVL, Red-Black) or skip list | | Minimizing/maximizing an answer with a feasibility check | The feasibility function is not monotonic | Dynamic programming or greedy approach | | Finding boundaries (first/last occurrence) in sorted data | Need all matching elements, not just boundaries | Two binary searches for range, then iterate | | Search space is very large (10^9+) but predicate is cheap | Predicate evaluation is expensive and search space is small | Linear scan may be faster for small n | | Finding peak/valley in bitonic sequences | Array has multiple peaks (not bitonic) | Segment tree or linear scan | ## Important Caveats - Binary search has two distinct families: **exact match** (`while lo <= hi`, return inside loop) and **boundary finding** (`while lo < hi`, return after loop). Mixing conventions from one family into the other is the #1 source of bugs. - In languages without arbitrary-precision integers (C, C++, Java, Go), always use the overflow-safe mid formula. Python and JavaScript (BigInt) do not have this issue for standard integers. - The "search on answer space" pattern is the most powerful generalization but requires proving that the feasibility predicate is monotonic. If feasibility is not monotonic, binary search will silently return wrong answers. - For floating-point binary search, use a fixed number of iterations (e.g., 100) instead of an epsilon comparison to avoid precision issues. `for i in range(100)` converges to machine precision. - When dealing with duplicates in rotated arrays, the worst-case time complexity degrades from O(log n) to O(n). Consider whether the problem guarantees distinct elements. ## Related Units - [Sorting Algorithms](/software/patterns/sorting-algorithms/2026) - [Two Pointer Technique](/software/patterns/two-pointer-technique/2026) - [Dynamic Programming](/software/patterns/dynamic-programming/2026)