Quickly finding the first point at which a function equals 0 using scipy.optimize

Question

Basically, given a function that produces outputs like this for different parameters:

I want to quickly find the first x at which the function equals 0. So with parameters that produce the blue curve over x, I want to find x=134. For the green curve, I want to find x=56, etc.

I think the function will always be monotonically decreasing until it hits zero, but I'm not totally sure.

The function is not necessarily monotonically decreasing.

I am sure that it will only hit 0 once, and then remain zero.

Currently I'm brute-forcing it by iterating through x values until I hit zero, but I want something that will be better at making educated guesses (based on slope?) and iterating.

Ideally I want to use something already-baked (since 90% of programmers can't even write a binary search correctly), like something from scipy.optimize, but it seems like those all want to find either a global minimum or a zero-crossing.

(This function is sort of a distance_to_the_wall of the RGB cube for a given chroma in Lch color space (so basically building a "sanely clip to RGB" function), but since the mapping between IRGB and LCh can vary by library and with parameters like illuminant etc. I think it's best to just try a few values until the right one is found rather than trying to reverse-calculate the value directly?)

Answer 1

Here is some code to flesh out @ExP's bisection/binary search answer:

def find_first_zero(func, min, max, tol=1e-3):
    min, max = float(min), float(max)
    assert (max + tol) > max
    while (max - min) > tol:
        mid = (min + max) / 2
        if func(mid) == 0:
            max = mid
        else:
            min = mid
    return max

Answer 2

Try bisection: Check if it's 0 in the middle of your interval; if it is, continue on the left, otherwise, on the right. Do the same thing with the reduced interval recursively until you're close enough. This method is of complexity O(log n) compared to yours, which is O(n).