Searching a range of answers
Drop the array. The candidates are the possible answers themselves, and the test is a question you can check for any one of them.
No array at all
The integer square root of 40 is the largest r with r² ≤ 40. There is no array to search, but the candidates 0, 1, 2, … 40 are in a line and the test "r² ≤ 40" is true up to the answer and false after it. That is everything binary search needs. The array was only ever a way of listing candidates.
Problems of this kind say "the largest x such that" or "the smallest x such that", and the x is a number you could check if someone handed it to you.
The search, step by step
A last-true search, so the midpoint rounds up (the first module showed what happens otherwise). The range starts at [0, 40]: 0 certainly passes, and no r above 40 can, because r² > r ≥ 40 once r > 40.
The integer square root of 40.
-
Step 1 / 7lo0hi40
Every r from 0 to 40 is still possible. We want the last one with r² ≤ 40.
-
Step 2 / 7lo0mid20hi40
20² = 400 > 40. 20 fails, so does everything above it: hi = 19.
-
Step 3 / 7lo0mid10hi19
10² = 100 > 40. 10 fails, so does everything above it: hi = 9.
-
Step 4 / 7lo0mid5hi9
5² = 25 ≤ 40. 5 works, so the answer is 5 or larger: lo = 5.
-
Step 5 / 7lo5mid7hi9
7² = 49 > 40. 7 fails, so does everything above it: hi = 6.
-
Step 6 / 7lo5mid6hi6
6² = 36 ≤ 40. 6 works, so the answer is 6 or larger: lo = 6.
-
Step 7 / 7answer6
lo and hi meet at 6: 6² = 36 ≤ 40 < 49 = 7². For the largest 32-bit input the same search needs about 31 tests; counting up would need 46,341.
Choosing the bounds
The range must contain the answer, and for the template to be valid the end that is assumed to pass must really pass. Get either wrong and the search returns a wrong number without complaint.
| Problem | Candidates | Why the bounds are safe |
|---|---|---|
| Integer square root of x | 0 to x (or x / 2 + 1) | 0 always passes; r > x fails for x ≥ 1 |
| Complete rows of n coins | 0 to n | k rows need k(k + 1) / 2 coins; 0 rows always fit, more than n rows never do |
| Smallest ship capacity | largest package to total weight | below the largest package nothing ships; the total ships in one day |
| Slowest rate that finishes in time | 1 to the largest queue | at the largest queue each queue takes one hour |
When you are not sure an end passes, widen the range by one candidate that stands for "none" (hi = n in the lower bound), or check the end before searching.
The test sets the cost
The search makes about log₂(range) calls to the test, so the total cost is that number times the cost of one test. For the square root the test is one multiplication. In the pattern modules at the end of this chapter the test is a pass over the whole input, O(n), and the search is O(n log range). With a range of 10⁹ that is about 30 passes.
R is the width of the range of candidates, not the length of any array.
Check that the test does not overflow. r × r for r near 46,341 exceeds 2³¹ − 1, and k(k + 1) / 2 for k near 65,536 does too. Use 64-bit integers, or rearrange: r ≤ x / r instead of r × r ≤ x.
The code
The integer square root with the last-true template, midpoint rounded up and the square computed in 64 bits.
def my_sqrt(x):
lo, hi = 0, x # the answer is in [lo, hi]
while lo < hi:
mid = (lo + hi + 1) // 2 # round up, or lo = mid never moves
if mid * mid <= x:
lo = mid # mid works; the answer is mid or larger
else:
hi = mid - 1
return lolong long solve(long long x) {
long long lo = 0, hi = x; // the answer is in [lo, hi]
while (lo < hi) {
long long mid = lo + (hi - lo + 1) / 2; // round up, or lo = mid never moves
if (mid * mid <= x) lo = mid; // 64-bit: mid < 2^31, so mid * mid < 2^62
else hi = mid - 1;
}
return lo;
}class Solution {
public int mySqrt(int x) {
long lo = 0, hi = x; // the answer is in [lo, hi]
while (lo < hi) {
long mid = lo + (hi - lo + 1) / 2; // round up, or lo = mid never moves
if (mid * mid <= x) lo = mid; // long: no overflow
else hi = mid - 1;
}
return (int) lo;
}
}function mySqrt(x) {
let lo = 0, hi = x; // the answer is in [lo, hi]
while (lo < hi) {
const mid = lo + Math.ceil((hi - lo) / 2); // round up
if (mid * mid <= x) lo = mid; // exact wherever it matters: near x the square is below 2^32
else hi = mid - 1;
}
return lo;
}fn solve(x: i64) -> i64 {
let (mut lo, mut hi) = (0i64, x); // the answer is in [lo, hi]
while lo < hi {
let mid = lo + (hi - lo + 1) / 2; // round up, or lo = mid never moves
if mid * mid <= x { lo = mid } else { hi = mid - 1 }
}
lo
}solve :: Int -> Int
solve x = go 0 x
where
-- the answer is in [lo, hi]; mid rounds up so that lo = mid always moves
go lo hi
| lo >= hi = lo
| mid * mid <= x = go mid hi
| otherwise = go lo (mid - 1)
where mid = lo + (hi - lo + 1) `div` 2The same code is the reference solution to Integer square root without a library, where it is compiled and run against the tests in all six languages.