Binary search

August 22, 2018

Slicker binary search: make jumps and then slow the speed of the jumps when you get closer to the target.

def binary_search(A, x):
    # assume sorted A as usual
    n = len(A)
    b, k = n//2, 0
    while b >= 1: # when b == 0 we've exhausted all window resolutions
        # b is the jump, k is the location
        while A[k+b] <= x and k+b < n:
            k += b
        b /= 2;
    if A[k] == x:
        return k

You can use this version of binary search to efficiently find where the value of a function changes (e.g. from False to True)

def change_search(ok, N):
    k = -1
    b = z = N # some index for which we know ok(N) == True
    while b >= 1:
        while !ok(k+b):
            k += b
    return k+1 # is the largest value which is False

You can then use this technique to $max$ of $ f $: find a position $k$ such that:

$ f\left( x \right) < f\left( x + 1 \right) $ when $ x < k $ and
$ f\left( x \right) > f\left( x + 1 \right) $ when $ x \geq k $

Hence the idea is use binary search to find largest value of $x$ such that $ f\left( x \right) < f\left( x + 1 \right) $

    def find_max_fn(fn, N):
       k = -1
       b = z = N
       while b >= 1:
           while fn(k+b) < f((k+b)+1):
               k += b
       return k+1