Sandeep Bhardwaj

Backend Engineer • SaaS Builder

Binary search is not just for finding a value in a sorted array. It is a decision pattern over monotonic spaces.

Core Idea

Maintain search range [lo, hi] and shrink by half based on a monotonic condition.

while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (condition(mid)) {
        hi = mid - 1; // or lo = mid + 1 based on variant
    } else {
        lo = mid + 1;
    }
}

Pattern 1: Exact Match

public int binarySearch(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Pattern 2: First True / Lower Bound

public int lowerBound(int[] nums, int target) {
    int lo = 0, hi = nums.length; // half-open
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] >= target) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Pattern 3: Search on Answer

When answer is numeric and feasibility is monotonic.

Example: minimum eating speed (Koko).

public int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = Arrays.stream(piles).max().orElse(1);

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canFinish(piles, h, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

private boolean canFinish(int[] piles, int h, int k) {
    long hours = 0;
    for (int p : piles) {
        hours += (p + k - 1) / k;
    }
    return hours <= h;
}

Common Mistakes

  1. Infinite loops from wrong boundary updates
  2. Mid overflow from (lo + hi) / 2
  3. Mixing closed [lo, hi] and half-open [lo, hi) styles
  4. Not proving monotonicity in answer-space problems

Debug Pattern (Fast)

When binary search fails, print:

  • lo, hi, mid
  • nums[mid] or feasibility result
  • update decision taken

Example:

lo=3 hi=7 mid=5 cond=true -> hi=5

You can usually spot off-by-one errors within a few iterations.

Post-Loop Validation Rule

For bound-style searches, loop exit index may still need validation.

Example for lower bound:

int idx = lowerBound(nums, target);
if (idx == nums.length || nums[idx] != target) return -1;

Always define what returned index means when target is missing.

  1. Binary Search (LC 704)
    LeetCode
  2. First Bad Version (LC 278)
    LeetCode
  3. Search Insert Position (LC 35)
    LeetCode
  4. Find First and Last Position (LC 34)
    LeetCode
  5. Koko Eating Bananas (LC 875)
    LeetCode
  6. Capacity To Ship Packages (LC 1011)
    LeetCode

Key Takeaways

  • Binary search is a monotonic decision framework.
  • Choose one interval convention and stay consistent.
  • Answer-space binary search is a high-value interview and production pattern.

Comments

You may also enjoy