Imagine you have a problem where you need to find a specific number — the magic number — that makes something just right. It’s not a guessing game; it’s more like hunting for a hidden switch that turns your code from broken to brilliant. This magic number might be a threshold, a limit, or a parameter that optimizes your algorithm.
Here’s the kicker: brute force rarely cuts it. If you have, say, a thousand candidates, trying all of them one by one can be painfully slow and often unnecessary. Instead, you want an approach that homes in on the magic number quickly and reliably.
Binary search is your best friend here. It’s the classic “divide and conquer” strategy that works when you can order your candidates and check whether a candidate is “too low” or “too high.” The search space halves with every test, which blows brute force out of the water.
JOIOT 128GB USB C Flash Drive Dual USB 3.0 Flash Drive Type C + USB A Portable Type-C Flash Drive 2-in-1 USB-C Thumb Drive for Smartphone Tablet Computer Mac iPhone 15 Black
$12.99 (as of August 11, 2025 13:08 GMT +03:00 - More infoProduct prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on [relevant Amazon Site(s), as applicable] at the time of purchase will apply to the purchase of this product.)Let’s say you have a function is_valid(x) that returns True if x is at or beyond the magic number, and False otherwise. Your task is to find the smallest x where is_valid(x) flips from False to True. Here’s how you do it:
def find_magic_number(low, high, is_valid):
while low < high:
mid = (low + high) // 2
if is_valid(mid):
high = mid
else:
low = mid + 1
return low
Notice the subtlety: when is_valid(mid) is True, we don’t just return mid. Instead, we keep looking left, because we want the smallest number that passes the test. That is the key to finding the “boundary” rather than just any valid number.
Let’s say you’re tuning a timeout setting. You want the smallest timeout that’s long enough for your process to succeed. You could write is_valid(timeout) to run the process with the given timeout and return whether it finished successfully. Then just call find_magic_number(min_timeout, max_timeout, is_valid) and boom — you’ve found your magic number.
Binary search assumes a monotonic property: once is_valid(x) is True for some x, it remains True for all larger x. If this isn’t the case, your life gets more complicated, but for many optimization tasks, this assumption holds true.
The real power is in how you implement is_valid. It’s a black box that tests your candidate. It might run a simulation, a test suite, or even a machine learning inference. The cheaper and faster this check, the quicker your search will be.
Sometimes, you don’t have precise bounds for low and high. In those cases, start with a reasonable guess and exponentially expand the search range until you find a value where is_valid is True. Then binary search within that range.
def find_magic_number_unbounded(is_valid):
low = 0
high = 1
while not is_valid(high):
low = high
high *= 2
return find_magic_number(low, high, is_valid)
This “exponential backoff” search saves you from needing exact bounds upfront. It’s a trick that pops up in all sorts of “searching for a threshold” problems.
Finding the magic number is less about luck and more about recognizing the problem’s structure. If your problem fits the “monotone predicate” model, binary search will get you there in O(log n) time — elegant, efficient, and satisfying.
Next you’ll want to understand how to zero in on the exact point where the value flips — the surprisingly simple art of hitting zero, but that’s a story for the next piece. For now, remember: knowing your predicate function and exploiting monotonicity turns hunting for magic numbers into a straightforward algorithmic dance, not a frantic shot in the dark.
Now find the lowest point in the valley
But the world isn’t always a neat monotonic sequence. Sometimes, you’re not looking for the edge of a cliff, but the bottom of a valley. Think about tuning a cache size. Too small, and you have constant cache misses, which is slow. Too large, and you have memory pressure and garbage collection overhead, which is also slow. The sweet spot—the lowest point in the latency valley—is somewhere in between. A simple binary search won’t work because the function is not monotonic; it goes down, then it goes up.
If you check a single point mid and find its performance value, you’re stuck. Is the true minimum to the left or to the right? You have no concept. The value func(mid) alone doesn’t give you a direction. This is where you need a slightly different approach. The classic textbook answer is ternary search.
The concept is to divide the search range into three parts using two midpoints, m1 and m2. Then you evaluate your function at both points. If func(m1) is less than func(m2), it implies that the minimum cannot be in the rightmost third of the range, because the function is already trending upwards by the time it gets to m2 (or at least, it’s not as low as it was at m1). So, you can safely discard the range [m2, high]. Conversely, if func(m2) is lower, you can discard the leftmost third, [low, m1]. You repeat this, shrinking the search space by a third each time.
def find_valley_ternary(low, high, func, iterations=100):
# This is for floating point numbers.
# For integer domains, the loop condition would be low <= high.
for _ in range(iterations):
# To avoid floating point precision issues, check if range is tiny
if abs(high - low) < 1e-9:
break
m1 = low + (high - low) / 3
m2 = high - (high - low) / 3
if func(m1) < func(m2):
high = m2
else:
low = m1
return (low + high) / 2
Ternary search works, but it feels a bit clunky with its two midpoints and floating-point division. There’s a more elegant way that leverages the power of binary search. The key insight is to change what you’re searching for. You aren’t searching for a value; you’re searching for a property. The minimum of the valley is the point where the function’s slope changes from negative to non-negative.
So, we can define a new predicate. Let’s check the local slope at mid by comparing func(mid) with func(mid + 1). If func(mid) > func(mid + 1), we are on the descending part of the valley. This means the true minimum must be to the right of mid. If func(mid) = func(mid + 1), we are either at the minimum or on the ascending part. In this case, the minimum must be at mid or to its left. This gives us a clear, binary decision to shrink our search space.
This transforms the problem back into a form that our original binary search can solve. We’re looking for the first point where the function stops decreasing. This modified binary search is generally preferred over ternary search because it is simpler, converges slightly faster, and is less prone to floating point shenanigans.
def find_valley_binary(low, high, func):
# This assumes an integer domain for simplicity
# high should be set to the max index, not len(array)
while low < high:
mid = low + (high - low) // 2
if func(mid) < func(mid + 1):
# We are on the ascending slope or at the minimum.
# The minimum could be mid, so we can't discard it. # The search space becomes [low, mid]. high = mid else: # We are on the descending slope. # The minimum must be to the right of mid. # The search space becomes [mid + 1, high]. low = mid + 1 # low is the index of the minimum element return lowNotice how this code is almost identical to the first binary search we wrote. The only thing that changed is the condition inside the if statement. Instead of checking against a fixed property like True, we check the local behavior of the function. This is a powerful technique: by reframing the question, you can often reuse a simple, powerful algorithm for a seemingly more complex problem. Finding the lowest point in a valley isn’t some dark art; it’s just another application of binary search, once you look at it the right way.
The terrifying list of methods and why you can ignore most of them
Now, let’s talk about the terrifying list of methods that often come up when you start searching for “magic numbers” or optimization points—and why you can safely ignore most of them.
First, there’s brute force. We already dismissed it, but it’s worth emphasizing why it’s so bad. Brute force means trying every possible candidate. If your search space is large, this becomes exponential or worse. It’s the default for beginners and the bane of performance. Don’t do it.
Next up: gradient descent and its fancy cousins. These methods are great when you have a smooth, differentiable function and you can compute gradients efficiently. But most “magic number” problems don’t give you that luxury. Your is_valid function might be a black box, noisy, or non-differentiable. Gradient descent requires careful tuning of learning rates and can get stuck in local minima. For discrete search spaces, it’s often overkill.
Simulated annealing and genetic algorithms are other “metaheuristics” that people throw at optimization problems. They’re cool, inspired by nature, and sometimes find good solutions where others fail. But they’re stochastic, slow, and unpredictable. If your problem has a monotone or unimodal structure, these are massive overkills. They’re more like bringing a bazooka to a knife fight.
Dynamic programming is another tempting approach. It excels when your problem breaks down into overlapping subproblems and optimal substructure. But if you’re just searching for a threshold or minimum in a unimodal function, dynamic programming adds unnecessary complexity.
So what should you focus on? The methods that exploit structure:
- Binary search on monotone predicates. The simplest, fastest, and most reliable.
- Ternary search on unimodal functions. A neat tool when the function dips and rises once.
- Exponential search. When you don’t know bounds, quickly find them before binary searching.
Here’s a quick summary in code form, showing you the skeletons of these methods so you can pick the right tool fast:
def binary_search(low, high, is_valid):
while low < high:
mid = (low + high) // 2
if is_valid(mid):
high = mid
else:
low = mid + 1
return low
def exponential_search(is_valid):
low, high = 0, 1
while not is_valid(high):
low = high
high *= 2
return binary_search(low, high, is_valid)
def ternary_search(low, high, func, iterations=100):
for _ in range(iterations):
m1 = low + (high - low) / 3
m2 = high - (high - low) / 3
if func(m1) < func(m2):
high = m2
else:
low = m1
return (low + high) / 2
Ignore the rest. If your problem fits any of these patterns, you’re set. If it doesn’t, you might be dealing with a genuinely hard problem, or you might have missed an important insight into your problem’s structure.
One last point: don’t confuse “optimization” with “searching.” Sometimes you’re trying to find a parameter that satisfies a condition (a yes/no question), which is ideal for binary search. Other times, you want to minimize or maximize a function, which might call for ternary search or other methods. Mixing these up leads to confusion and wasted effort.
And remember, these methods shine brightest when your function evaluations are expensive. If your checks are cheap, brute force might be fine. But if each check is a lengthy test suite run, a long simulation, or a costly database query, then the difference between O(n) and O(log n) is not just theoretical—it’s the difference between finishing before lunch and finishing next week.
Here’s a practical example showing how you might combine exponential and binary search to find the smallest number x where some expensive condition becomes true:
def expensive_check(x):
# Imagine this runs a slow test or simulation
# For demo, say valid if x >= 12345
return x >= 12345
def find_threshold():
# First, find bounds using exponential search
low, high = 0, 1
while not expensive_check(high):
low = high
high *= 2
# Now binary search within bounds
while low < high:
mid = (low + high) // 2
if expensive_check(mid):
high = mid
else:
low = mid + 1
return low
print(find_threshold()) # Outputs: 12345
Notice how the code is clean, concise, and leverages the problem’s monotonicity. No complex heuristics, no tuning parameters, just solid algorithmic thinking.
In contrast, if you tried to use gradient descent or simulated annealing here, you’d waste time tuning hyperparameters and still might not land exactly on 12345. Binary search gives you the guarantee: if the predicate is monotone, you’ll find the exact boundary.
So, before you dive into complex methods, ask yourself: does my problem have a monotone predicate or a unimodal function? If yes, pick binary or ternary search. If not, maybe it’s time to rethink the problem or accept approximate solutions.
And with that, you’re ready to tackle the next challenge: how to handle noisy or approximate is_valid functions where the boundary isn’t perfectly sharp, or where evaluations have randomness. But that’s a tale for another time. For now, you’ve tamed the terrifying list and picked your weapons wisely.
Source: https://www.pythonfaq.net/how-to-find-roots-and-optimize-functions-with-scipy-optimize-in-python/
