Binary Search and Approximations

Suppose someone thinks of an integer between 1 and 1000 (inclusive). You can ask "Is it less than, equal to, or greater than X?" and they will answer honestly.

Question 1: If you always guess randomly, how many guesses might you need in the worst case?

Question 2: If you always guess the middle of the remaining range, how many guesses do you need in the worst case? Try it on paper for the range [1, 1000].

Key insight: Each "guess the middle" halves the range. After k guesses the range has shrunk from 1000 to roughly $1000 / 2^k$. How many times can you halve 1000 before you reach 1?

# How many halvings to go from n to 1?
# Each step: n -> n/2 -> n/4 -> ...
# After k steps: n / 2^k <= 1  →  k >= log2(n)

Write a function count_halvings(n) that returns how many times you can halve n (starting from a whole number) before reaching 1 or below.

count_halvings(1000)  # about 10
count_halvings(1)     # 0
count_halvings(16)    # 4

The square root of n is the number x such that x * x = n. For example, sqrt(25) = 5 because 5 * 5 = 25.

Before you code — think about the search:

If you want sqrt(25), you know the answer is between 0 and 25. Why?

Now suppose you could make one guess to narrow that range as much as possible. What single guess would eliminate the most possibilities? And once you check that guess, how do you decide which half of the range to keep?

Keep narrowing until mid * mid is within precision of n.

Write sqrt_binary_search(n, precision) that returns an approximation of sqrt(n).

Arguments:

• n: a non-negative number
• precision: how close mid*mid must be to n (e.g., 0.0001)

Before you code:

• What is the initial low? What is the initial high?
• When mid*mid < n, should you move low or high to mid?
• When does the loop stop?

Run the plotting helper below to see how the search interval [low, high] narrows with each step.

The cube root of n is the number x such that x * x * x = n. For example, cuberoot(27) = 3 because 3 * 3 * 3 = 27.

This is more interesting than sqrt because:

• The cube root of a negative number is also negative (cuberoot(-8) = -2).
• For |n| < 1, the cube root is larger than |n| (cuberoot(0.001) = 0.1).

Before you code — think about these cases:

1. cuberoot(27): search range [0, 27]. Standard.
2. cuberoot(-64): cube root of |-64| = 4, then negate → -4.
3. cuberoot(0.001): |n| < 1, so the answer is between 0 and 1, not 0 and 0.001. Use range [0, 1] when |n| < 1.

Stopping rule: Stop when abs(mid**3 - abs(n)) < precision.

Write cuberoot_binary_search(n, precision).

You already built sqrt_binary_search — adapt it. The core binary search loop is the same; what changes is the check and the edge cases.

Think about:

• What do you check instead of mid * mid?
• Negative numbers: what is (-2)³? How can you handle negatives by working on abs(n) and fixing the sign at the end?
• Numbers between -1 and 1: cuberoot(0.001) = 0.1, which is larger than 0.001. What does that mean for your initial high?

You just wrote sqrt_binary_search and cuberoot_binary_search. Look at them side by side. The only thing that changes is the check function:

Before you code:

• What range should low and high be for the nth root?
  • If x >= 1: range is [0, x] (the nth root is always ≤ x for n ≥ 1).
  • If 0 < x < 1: the nth root is larger than x, so use range [0, 1].
• For odd n, negative x values have real roots. For even n, they do not.

Write nth_root(x, n, precision=1e-9) that returns the real nth root of x.

For simplicity, assume x ≥ 0 (handle negatives as a bonus below).

Python can compute nth roots with x ** (1/n). Verify that your function gives the same answer for a range of values.

Binary search works for square root, cube root, and nth root. What property of these functions makes binary search possible?

A. They all use exponents

B. They are all monotonically increasing — a larger input always gives a larger output, so the midpoint test tells you which half to keep

C. They all return values between 0 and 1

D. They can all be computed without importing any library

So far you searched for a VALUE x such that x**n == target. Now flip the problem: search for an EXPONENT y such that 10**y == x.

This is exactly the definition of the logarithm:

$$\log_{10}(x) = y \quad \Leftrightarrow \quad 10^y = x$$

Why does binary search still work? The function $f(y) = 10^y$ is strictly increasing. So if 10**mid < x, the true exponent must be larger: move low = mid. If 10**mid > x, move high = mid.

Before you code — think about the bracket:

Before you can search, you need to know where to look. How would you find a range [low, high] such that the answer is definitely inside? Think about what 10**0 and 10**1 equal — when do you need to look beyond that range? What about when x < 1?

Write log10_binary_search(x, tol=1e-7).

You have already built binary search for roots — this is the same idea applied to exponents. The new challenge is figuring out the initial search bracket, since the exponent could be any real number.

Run the plotting helper below to visualise the search for the exponent y such that $10^y = x$.

Now generalise: instead of searching for y such that 10**y == x, search for y such that n**y == x for any base n.

When n > 1: $f(y) = n^y$ is strictly increasing. Same logic as log10.

When 0 < n < 1: $f(y) = n^y$ is strictly decreasing. For example: $0.5^2 = 0.25 < 0.5^1 = 0.5$. As y increases, $n^y$ decreases.

For the case 0 < n < 1, the comparisons flip:

• If n**mid > x, we need a larger exponent → low = mid.
• If n**mid < x, we need a smaller exponent → high = mid.

Before you code:

• Verify by hand: log_base_n(0.04, 5) = -2 because $5^{-2} = 1/25 = 0.04$.
• With base=5 (> 1), $f(y) = 5^y$ is increasing. x=0.04 < 1 so y must be negative. Start with low=-1, high=0; keep low *= 2 until 5**low <= 0.04.

Raise ValueError if x <= 0, n <= 0, or n == 1.

Write log_base_n(x, n, tol=1e-7).

The bracket-finding logic is the same as log10, but with n**y instead of 10**y. For 0 < n < 1, you will need to flip the comparison in the binary search step.

The change of base formula says:

$$\log_b(x) = \frac{\log_a(x)}{\log_a(b)}$$

Verify this using your log_base_n function: log_base_n(x, b) should equal log_base_n(x, a) / log_base_n(b, a) for any a.

# log2(8) using base-10 logs:
# log10(8) / log10(2) = log2(8)

Everything so far searched a continuous range of numbers. But the same halving idea works on a sorted array — and this is the version you will meet everywhere, from databases to bisect in the standard library.

The setup changes slightly:

• Instead of lo and hi being numbers, they are indices into the array.
• Instead of stopping at a precision, you stop when the indices cross.

Write contains(arr, x) that returns True if x occurs in the sorted list arr. Look at the middle element, decide which half could contain x, and repeat. No in, no walking the whole list: for a million items your function should look at ~20 elements at most.

If the array has duplicates, "is it there" isn't enough — you often need where does it start and where does it end.

Write find_first(arr, x) and find_last(arr, x) that return the index of the first / last occurrence of x in the sorted list arr, or -1 if it's absent.

Hint: when you find a match, don't stop — remember the index, then keep searching the half where an even earlier (or later) match could still hide.

A sensor logs a billion readings, each one 0, 1 or 2, and the log is sorted. Your boss wants to know how many 1s there are. Walking the array is a billion steps; you can answer it in about sixty.

Write count_val(arr, x) that returns how many times x occurs in the sorted list arr, by combining find_first and find_last.

You have a small list of IDs and a huge sorted list of registered IDs, and you want the ones that appear in both. Checking each small ID against every huge ID costs $m \times n$ comparisons; binary-searching each small ID costs only $m \times \log(n)$.

Write commons(small, huge) that returns the elements of small (in order) that occur in the sorted list huge. Reuse your contains.

One last twist. This array isn't sorted — it goes down, then up, like a valley:

[10, 9, 8, 6.5, 4.1, 3.2, 2, 4, 4.5, 6]

Binary search still works! Compare arr[mid] with arr[mid + 1]:

• if arr[mid] > arr[mid + 1], you are on the downhill slope — the minimum must be to the right;
• otherwise you are on the uphill slope (or at the bottom) — the minimum is at mid or to its left.

Write find_min_convex(arr) that returns the minimum value of such a valley-shaped array.

Hold on to this idea: "walk downhill until it stops going down" is exactly how gradient descent trains machine-learning models — you will meet it again in the Gradient Descent chapter.

A sorted list has 1,000,000 elements. What is the maximum number of comparisons binary search needs to find an element (or confirm it's missing)?

A. 1,000,000

B. 1,000

C. About 20

D. About 500,000