Binary Search using Geometric Means

Question

Background: When doing a binary search on an array, we initialise an upper h and lower l bound and test the mid-point (the arithmetic mean) half-way between them m := (h+l)/2. Then we either change the upper or lower bound and iterate to convergence.

Question: We can use a similar search strategy on the (unbounded) real numbers (well their floating point approximation). We could use a tolerance of convergence to terminate the search. If the search range is on the positive real numbers (0<l<h), we could instead take the geometric mean m :=(hl)^.5. My question is, when is the geometric mean faster (taking few iterations to converge)?

Motivation: This cropped up when I tried a binary search for a continuous variable where the initial bounds were very wide and it took many iterations to converge. I could use an exponential search before a binary search, but I got curious about this idea.

What I tried: I tried to get a feel for this by picking a million random (floating point) numbers between 2 and an initial h that I picked. I kept the initial l=1 fixed and the target had to be within a tolerance of 10^-8. I varied h between 10^1 and 10^50. The arithmetic mean had fewer iterations in about 60-70% of cases.

But the geometric mean is skewed (below the arithmetic mean). So when I restricted the targets to be less than the geometric mean of the initial bounds sqrt(lh) (still keeping l=1) the geometric mean was almost always faster (>99%) for large h>10^10. So it seems that the both h and the ratio of target / h could be involved in the number of iterations.

Code Example: Here's a simple Julia code to demonstrate:

function geometric_search(target, high, low)
    current = sqrt(high * low)
    converged = false
    iterations = 0
    eps = 1e-8

    while !converged
        if abs(current - target) < eps
            converged = true
        elseif current < target
            low = current
        elseif current > target
            high = current
        end

        current = sqrt(high * low)
        iterations += 1
    end
    return iterations
end

target = 3.0 
low = 1.0 
high = 1e10

println(geometric_search(target, high, low))

Answer 1

The heart of this problem is "how fast is a geometric-mean binary search?"

In an ordinary (arithmetic mean) binary search among n discrete elements, the number of steps is s = log₂n (in the large n limit). In the continuous case, if we are searching for an interval of size d in a larger interval of size R, the number of steps is s = log₂(R/d).

Now consider the continuous case, but using the geometric mean. We are searching over a continuous variable x for an interval [k, k+d] in a larger interval [l, h], and our first test will be (lh)^1/2. Now we "take the log of the whole problem", which is to say we change to a new variable y which is defined as ln(x). So now we are searching for the interval [ln(k), ln(k+d)] in the larger interval [ln(l), ln(h)], and our first test will be y=(ln(l)+ln(h))/2. This is an arithmetic-mean binary search in y, but the size of the target varies according to its location. The number of steps will be

s = log₂((ln(h)-ln(l))/(ln(k+d)-ln(k)))
= log₂(ln(h/l)/ln((k+d)/k))

And notice that ln((k+d)/k) = ln(1 + d/k).

So the number of steps to find the target depends on k, the location of the target. Targets nearer to the low end of the range will be bigger, and will therefore be found more quickly than targets nearer the higher end. Near the low end, geometric-mean searches are faster than arithmetic-mean, and near the high end, arithmetic-mean are faster than geometric mean.

So where is the critical point? When will arithmetic-mean and geometric-mean searches be equally fast? We set the number of steps equal:

log₂(ln(h/l)/ln(1 + d/k)) = log₂((h-l)/d)
ln(h/l)/ln(1 + d/k) = (h-l)/d

And solve for k:

ln(1 + d/k) = d ln(h/l)/(h-l)
1 + d/k = (h/l)^d/(h-l)
d/k = (h/l)^d/(h-l) - 1
k = d/((h/l)^d/(h-l) - 1)

(This seems correct, but I have not yet written code to test it.)