The answer is a real number, not an integer or an index. It can be a height, a distance, a water level or an average, which can fall between any two values. The problem accepts the answer within a tolerance such as 10^-5. An answer counts as correct when it differs from the true value by at most 0.00001. The answer can also be a fraction you must rank. A guess is easy to check, and the check flips only once as the guess grows.

lo always fails the check and hi always passes it, so the answer is always between them, and each round halves that window.

real-valued answer (accepted within a tolerance such as 10^-5 = 0.00001, or a ratio or fraction) ➔ move lo or hi onto mid for a fixed number of rounds ➔ answer within the tolerance

A real number has no next value after mid. So lo = mid + 1 and hi = mid - 1 have no value to step to. Instead, move one end onto mid itself. Set hi = mid when is_feasible(mid) passes, and set lo = mid when it fails. In the code for Separate Squares I (LC 3453), the check is 2 * part >= total - 2 * full. It passes when at least half of the total area is below the line y = mid. lo always fails the check and hi always passes it. So the answer never leaves the window between lo and hi. Each round halves that window. So a fixed number of rounds, for _ in range(100), makes the window far narrower than 10^-5. 10^-5 is 0.00001, the largest error the problem accepts. The same loop also finds the highest value that passes. For that, give the failing end as lo, even though it is the larger number. The trap is the integer loop while lo < hi, which never ends on floats. After enough rounds, lo and hi are neighbouring floats. Then mid equals lo or hi, so hi = mid or lo = mid changes nothing.

The values being ranked are whole numbers, the pair distances in Find K-th Smallest Pair Distance (LC 719): the k-th smallest is an integer the value search lands on exactly with lo = mid + 1, and there is nothing to snap.

Adding the whole squares and the cut squares into one float

A float keeps only about 16 significant digits. The whole squares can add up to a huge area, around 1011 here. At that size, the smallest step a float can hold is about 0.00006. When the small slice of a cut square, like 0.99997, is added to that sum, it is rounded to 1.0. The check then passes for a mid that is slightly too low. So hi = mid moves the window below the true answer. The loop is correct. The check is wrong. The fix keeps the two kinds of area apart. full holds the squares wholly below mid, and it is an exact integer. part holds only the squares that mid cuts, so it stays small. total - 2 * full is integer arithmetic, so the huge numbers cancel exactly. The float 2 * part is then compared against a small exact number. In the example, the check becomes 2 * part >= 2, which flips exactly at mid = 1000001. A quick test before coding: multiply the largest value in a float sum by 10^-16. The result must be far smaller than the tolerance. Here 1011 * 10^-16 = 10^-5, which is the tolerance itself, so there is no margin.

Looping while lo < hi on floats

Between two floats there is only a limited number of other floats. After enough rounds, lo and hi are neighbouring floats. Then mid = (lo + hi) / 2 equals lo or hi. In the example, mid equals hi and the check passes. So hi = mid changes nothing, and the loop never ends. for _ in range(100) stops after 100 rounds.

Stopping on hi - lo > eps with a tiny eps

Near 109, two neighbouring floats are about 1.2e-7 apart. So hi - lo can never drop below 1e-9 there, and the loop never ends. A fixed number of rounds always ends. Each round halves the window, so t rounds leave (hi - lo) / 2^t. A window of 2 * 109 needs 48 rounds to get below 10^-5, so 100 rounds is a safe default.

Writing > instead of >= in the area check

Sometimes a whole stretch of lines splits the area in half. In the example, every line from y = 1 to y = 2 does. With >=, a balancing mid moves hi down, so the search keeps the lowest line, 1. With >, a balancing mid moves lo up, so it returns the highest line, 2.

Not knowing what lo and hi hold at the end

The invariant tells you what each end means. lo always fails the check, and hi always passes it. After 100 rounds they are neighbouring floats, so the answer sits between them. hi is the lowest value known to pass. lo is the highest value known to fail. For "find the smallest h that balances", return hi. Both ends are within 10^-5 of the answer, so lo is usually accepted too. But lo is the failing side, and it lands slightly below the answer. return mid is worse. mid is only the last guess, and it may be on either side. If the problem asks for the highest value that passes, the roles swap. The passing end is then the lower number, and you return that one.

Returning hi when the answer is an exact fraction

return hi gives a float close to the answer, not the answer itself. K-th Smallest Prime Fraction (LC 786) asks for the fraction as [numerator, denominator]. The standard way to get it is one more pass after the rounds. It finds the largest fraction that is at most hi. best = [0, 1] starts at the fraction 0 / 1, which is smaller than every fraction in the input. For each denominator arr[j], i moves forward while arr[i] <= hi * arr[j]. Then arr[i - 1] / arr[j] is the largest fraction with denominator arr[j] that is at most hi. It replaces best when it is larger, and the comparison arr[i - 1] * best[1] > best[0] * arr[j] multiplies integers, so it is exact. The pass is safe because the final window is narrower than the smallest gap between two different fractions. There that gap is at least 1 / (3 * 104)^2.

Comparing two fractions with / instead of *

a / b > c / d rounds each fraction to a float before it compares them. A float keeps only about 16 significant digits. So two fractions that differ by less than that become the same float, or swap order. a * d > c * b asks the same question, because b and d are positive. It multiplies integers, and Python integers are exact at any size. So the answer is always right. In K-th Smallest Prime Fraction (LC 786), two different fractions differ by at least 1 / (3 * 104)^2, so / happens to work there. * needs no such check. Also * never divides by zero. The same rule does not make arr[i] <= mid * arr[j] exact when mid is a float. There mid * arr[j] is rounded once, just like arr[i] / arr[j]. That is why the last step compares the fractions as integers.