TryBugHunt
javaInfinite loopHard

Price search freezes when the budget falls between two prices

BugFind the bug and fix the code

What it should do

prices is sorted from cheapest to most expensive. firstAtLeast(prices, budget) uses binary search to return the index of the first price that is at least budget, or prices.length if none is, so firstAtLeast([1, 3, 5], 4) returns 2.

What happens instead

firstAtLeast([1, 3, 5], 4) never returns and the run times out. firstAtLeast([1, 3, 5], 1) returns 0 correctly.

public class Main {
    static int firstAtLeast(int[] prices, int budget) {
        int lo = 0;
        int hi = prices.length;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (prices[mid] < budget) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

Test a custom input to verify an edge case (e.g. empty lists, negative numbers, duplicates).

⏱️0:00
Hints
🏆 0 hints = Flawless Solve
Think & Test Cooldown
2:00 remaining

Take a moment to read the bug symptom and trace the code with Run & Check before unlocking Hint 1.

Hint 2
Unlocks after Hint 1
Hint 3
Unlocks after Hint 2

This bug belongs to the infinite loops pattern

The loop condition never becomes false, so the program runs until it is stopped.

What you'll practise

A hard Java debugging exercise about infinite loops: the loop condition never becomes false, so the program runs until it is stopped.

The checks your fix must pass

Signs of this kind of bug

Spoiler: why this bug happens(try it first; the hints get warmer one at a time)

Binary search only ends if every pass makes the range [lo, hi) smaller. When prices[mid] is too small, mid itself is ruled out, so the next range should start at mid + 1. Setting lo = mid keeps mid in the range. Once lo and hi are next to each other, mid = (lo + hi) / 2 equals lo, so lo = mid changes nothing and the loop repeats forever. Searches whose answer is near the start happen to move only hi and finish, which is why some inputs work. For each branch of a binary search, check that the range shrinks even when hi is lo + 1.

The pattern behind it: infinite loops.

More infinite loops to practise

Embed this challenge on your site

Paste this into any web page or blog post. Visitors fix the bug right there, in their browser.

<iframe src="https://trybughunt.com/embed/36771126-9566-466a-b805-7c44f5250e61" title="Debugging challenge: Price search freezes when the budget falls between two prices" width="100%" height="580" loading="lazy" style="border:1px solid #d4d4d8;border-radius:12px;max-width:760px"></iframe>
<p style="font-size:14px">Debugging challenge from <a href="https://trybughunt.com/challenges/36771126-9566-466a-b805-7c44f5250e61">TryBugHunt</a></p>