Obsidian Notes

_List_Binary_Search

4 min read

  1. The N-th root of an integer
  2. Matrix Median
  3. Single Element in a Sorted Array
  4. 5. Search in Rotated Sorted Array
  5. Median of Two Sorted Arrays
  6. Kth element of 2 sorted arrays
  7. Allocate Minimum Number of Pages
  8. Aggressive Cows

This is the #1 most common point of confusion in Binary Search.

Whether you use l <= r or l < r depends entirely on how you update your pointers (l and r) and where you return the answer.

Comparison at a Glance

FeaturePattern 1: while (l <= r)Pattern 2: while (l < r)
Search SpaceRange [l, r] until empty (l > r)Shrinement until 1 element remains (l == r)
Check inside loopDirect match check (return nums[mid])Condition check to eliminate half the array
Pointer updatesl = mid + 1 AND r = mid - 1l = mid + 1 AND r = mid (or m)
Return statementReturns inside the loop (or -1 outside)Returns after the loop (return nums[l])

Pattern 1: while (l <= r) — The “Find & Return” Pattern

Use this when you can directly identify if mid is your answer during the current iteration.

Key Mechanics:

  1. You explicitly check: “Is nums[mid] the target/answer?”
  2. If yes return nums[mid] immediately.
  3. If no You know for sure mid is NOT the answer, so you can safely exclude mid from both sides:
  • l = mid + 1
  • r = mid - 1
  1. The loop stops when l > r (search space becomes 0).

Example (Subarray Size Check for Single Element):

while (l <= r) {
    int m = l + (r - l) / 2;
 
    // 1. Direct check: Is 'm' the single element?
    if ((m == 0 || nums[m] != nums[m - 1]) && 
        (m == n - 1 || nums[m] != nums[m + 1])) {
        return nums[m]; // FOUND IT! Return immediately.
    }
 
    // 2. Safely eliminate 'm' from both sides
    if (leftSizeIsOdd) {
        r = m - 1; // 'm' is definitely not it, exclude 'm'
    } else {
        l = m + 1; // 'm' is definitely not it, exclude 'm'
    }
}
return -1;

Pattern 2: while (l < r) — The “Boundary Shrinking” Pattern

Use this when you cannot easily check if mid is the answer directly, or when mid might still be a potential candidate for the final answer.

Key Mechanics:

  1. You do NOT return inside the loop.
  2. You only ask: “Is the answer on the right side, or could it be at/left of mid?”
  3. Because mid might still be the single element, you **cannot do r = mid - 1**. You must keep mid in your search space by doing r = mid.
  4. The loop stops as soon as l == r (only 1 element left in the search space). That remaining element must be the answer.
  5. Return nums[l] after the loop ends.

Example (mid ^ 1 XOR Trick for Single Element):

while (l < r) {
    int m = l + (r - l) / 2;
 
    if (nums[m] == nums[m ^ 1]) {
        l = m + 1; // Pair is valid -> answer is strictly to the right
    } else {
        r = m;     // Answer COULD be 'm' itself, so don't do 'm - 1'!
    }
}
 
// Loop terminates when l == r (Search space shrunk to 1 element)
return nums[l];

How to Choose in an Interview (Simple Rule of Thumb)

  • Ask yourself: “Can I write an if statement to check if nums[mid] is the answer RIGHT NOW?”

  • YES Use while (l <= r).

  • Update: l = mid + 1 and r = mid - 1.

  • Return inside the loop.

  • NO (or it requires ugly boundary checks) Use while (l < r).

  • Update: l = mid + 1 and r = mid.

  • Return nums[l] after the loop.