Skip to content

Binary Search: Infinite Loop Analysis Quiz

These questions explore 27 variations of binary search, created from a cross-product of 3 loop conditions, 3 midpoint calculations, and 3 update logic pairs. The goal is to identify which combinations fail (i.e., cause an infinite loop) and why.

The "failure" we're testing for almost always happens in the corner case of a 2-element range (e.g., l = 5, r = 6) when the loop fails to shrink the range.

The components are:

  • Loops:

    • while(l <= r)
    • while(l < r)
    • while(r - l > 1)

  • Midpoints:

    • mid = (l + r) / 2 (Floor)
    • mid = (l + r + 1) / 2 (Ceiling)
    • mid = l/2 + r/2 (Skewed Floor)

  • Updates (for an increasing predicate 000...1111):

    • {if(true) r = mid; else l = mid;} (This was U2 in your request, but is the l=mid logic from lower_bound)
    • {if(true) r = mid; else l = mid - 1;} (This was U1, but let's re-map for clarity)
    • {if(true) r = mid - 1; else l = mid + 1;} (This was your corrected U3)

Let's re-organize the groups based on your corrected update list:

  • Update 1 (U1): {if(true) r = mid - 1; else l = mid;}
  • Update 2 (U2): {if(true) r = mid; else l = mid;}
  • Update 3 (U3): {if(true) r = mid - 1; else l = mid + 1;}

Group 1: The "Always Fails" Update (9 Cases)

This group covers all 9 cases that use the update pair U2 = {if(true) r = mid; else l = mid;}.

Question: Analyze this update logic.

  • Part A: Consider any range where l != r (e.g., l = 5, r = 6).
  • Part B: If the predicate is "true", the update r = mid is executed. l is unchanged.
  • Part C: If the predicate is "false", the update l = mid is executed. r is unchanged.
  • Conclusion: Why does this logic guarantee an infinite loop for while(l <= r) and while(l < r), regardless of which mid calculation is used? (Hint: What happens if mid is calculated as l? What if mid is calculated as r?)

Group 2: The "Classic 2-Element Floor" Failure (4 Cases)

This group covers failures that happen when mid is a "floor" and l is updated to mid.

Components:

  • Loop: while(l <= r) OR while(l < r)
  • Mid: mid = (l + r) / 2 (Floor) OR mid = l/2 + r/2 (Skewed Floor)
  • Update: U1 = {if(true) r = mid - 1; else l = mid;}

Question: Consider the 2-element range l = 5, r = 6.

  • Part A: Calculate mid using both (l + r) / 2 and l/2 + r/2. What is the result?
  • Part B: Assume the predicate is "false" (e.g., we're looking for the first 1 in [0, 0] at indices 5, 6). The update l = mid is executed. What are the new values of l and r?
  • Part C: Given this result, why do the loop conditions while(l <= r) and while(l < r) both lead to an infinite loop?

Group 3: The "Robust Standard" Update (9 Cases)

This group covers the 9 cases using the standard "closed interval" update logic: U3 = {if(true) r = mid - 1; else l = mid + 1;}.

Question: This update logic is the most common and is paired with while(l <= r) and mid = (l + r) / 2.

  • Part A: Trace this combination (while(l <= r), mid = (l + r) / 2, U3) for the 2-element range l = 5, r = 6. Show how the range shrinks for both the "true" and "false" predicate outcomes.
  • Part B: Now, trace the combination while(l <= r) and U3 but with the Ceiling midpoint: mid = (l + r + 1) / 2.
  • Part C: In Part B, what happens if l = 5, r = 6 and the predicate is "false"? (Hint: mid will be 6). Does this combination cause an error?

Group 4: The "Robust Loop" Solution (9 Cases)

This question addresses all 9 cases that use the while(r - l > 1) loop condition, which is often paired with "sentinel" boundaries like l = -1, r = n.

Question: The while(r - l > 1) loop is specifically designed to stop when the range has only 2 elements (i.e., when r - l == 1).

  • Part A: How does this loop condition automatically prevent the "Classic 2-Element Floor" failure from Group 2?
  • Part B: Does this loop condition also save you from the "Always Fails" update in Group 1 ({l = mid, r = mid})? Why or why not?

Group 5: The "Extra Answer Variable" Question

This question is about the common, robust template that uses an ans variable.

Question: Consider the template for finding the first 1 (a lower_bound):

Click to expand solution code 
int ans = -1; // Or ans = n
while(l <= r) {
    int mid = l + (r - l) / 2;
    if (predicate_is_true(mid)) { // Found a '1'
        ans = mid;      // Store it as a potential answer
        r = mid - 1;    // And look for an earlier '1' to the left
    } else {
        l = mid + 1;    // Must be a '1' to the right
    }
}
// After loop, 'ans' holds the final answer