DEV Community

Dev Cookies
Dev Cookies

Posted on

Binary Search Patterns Series — Blog 5: Cheat Sheet & Edge Cases

This is your one-stop guide for all binary search patterns, templates, and edge cases in Java.

1. Classic Binary Search (Sorted Arrays) 

public int binarySearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;

    while (low <= high) {
        int mid = low + (high - low)/2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}
Enter fullscreen mode Exit fullscreen mode

Variants:

  • First occurrence → update high = mid - 1 when found
  • Last occurrence → update low = mid + 1 when found
  • Count occurrences → last - first + 1
  • Insert position → return low

2. Binary Search on Monotonic Functions / Answer Search

Template:

long low = 0, high = 1_000_000_000;
while (low < high) { // strict <
    long mid = low + (high - low)/2;
    if (check(mid)) high = mid; // condition satisfied
    else low = mid + 1;          // not satisfied
}
return low; // smallest x satisfying condition
Enter fullscreen mode Exit fullscreen mode

Tips:

  • Define check(mid) clearly
  • Use long for large numbers
  • Be careful with low < high vs low <= high

Example Problems: Koko eating bananas, ship packages, minimum time tasks

3. Rotated / Special Arrays

Rotated Sorted Array (No Duplicates) 

if (arr[low] <= arr[mid]) { // left sorted
    if (target >= arr[low] && target < arr[mid]) high = mid - 1;
    else low = mid + 1;
} else { // right sorted
    if (target > arr[mid] && target <= arr[high]) low = mid + 1;
    else high = mid - 1;
}
Enter fullscreen mode Exit fullscreen mode

With Duplicates:

  • If arr[low] == arr[mid] == arr[high], increment low++, decrement high--

Bitonic / Mountain Array Search:

  • Find peak → binary search in ascending part → binary search in descending part

4. Binary Search in 2D / Matrix

Flattened Matrix Search 

int val = matrix[mid/cols][mid%cols];
Enter fullscreen mode Exit fullscreen mode

Staircase Search (O(m+n)) 

int row = 0, col = matrix[0].length - 1;
while (row < rows && col >= 0) {
    if (matrix[row][col] == target) return true;
    else if (matrix[row][col] > target) col--;
    else row++;
}
Enter fullscreen mode Exit fullscreen mode

5. Infinite / Unknown Size Array Search

  1. Exponentially expand range: high = 1, 2, 4, 8…
  2. Apply classic binary search within [low, high]

6. Ternary Search (Unimodal Function) 

double mid1 = left + (right - left)/3;
double mid2 = right - (right - left)/3;
if (f(mid1) < f(mid2)) left = mid1;
else right = mid2;
Enter fullscreen mode Exit fullscreen mode
  • Used for maximizing/minimizing unimodal functions

7. Edge Cases & Best Practices

  1. Overflow-safe mid: mid = low + (high - low)/2
  2. Empty array: arr.length == 0
  3. Single element array → check bounds
  4. All elements same → rotated array, duplicates handling
  5. Target outside bounds → return -1 or low/high accordingly
  6. Ceiling division for answer search: (x + y - 1)/y

8. Quick Reference Table

Pattern Condition Loop Key Tip
Classic Array Sorted array low ≤ high mid = low + (high-low)/2
First / Last Occurrence Sorted with duplicates low ≤ high adjust low/high when found
Answer Search Monotonic function low < high define check(mid)
Rotated Array Sorted + rotation low ≤ high check which half is sorted
Bitonic / Mountain Increase then decrease low ≤ high find peak first
2D Matrix Row+col sorted depends flatten or staircase search
Infinite Array Unknown size expand then binary search exponential expansion
Ternary Search Unimodal left+right precision-based stopping

9. Recommended Problems by Pattern

  • Classic: 704, 35, 34
  • Answer Search: 875, 1011, 774
  • Rotated Array: 33, 81, 153
  • Bitonic / Mountain: 852, 1095
  • 2D Matrix: 74, 240
  • Infinite Array: GfG variants
  • Ternary Search: Optimization problems, peak finding

✅ Blog 5 Summary:
This is your complete cheat sheet. After this, you can confidently tackle any binary search variant in interviews and competitive programming.

Top comments (0)