shifter_binary_search.py

def search(xs, b, e, x):
    if b==e:
        return b if xs[b] == x else -1
    m = (b+e)/2
    # [x_b .. x_m x_{m+1} .. x_e]
    # x_b <= x_m and x_{m+1} <= x_e # normal, normal
    if xs[b] <= xs[m] and xs[m+1] <= xs[e]:
        if xs[b] <= x <= xs[m]:
            return search(xs, b, m, x)
        if xs[m+1] <= x <= xs[e]:
            return search(xs, m+1, e, x)
        return -1
    # x_b <= x_m and x_{m+1} >= x_e # normal, shifted
    elif xs[b] <= xs[m] and xs[m+1] >= xs[e]:
        if xs[b] <= x <= xs[m]:
            return search(xs, b, m, x)
        if xs[m+1] <= x or x <= xs[e]:
            return search(xs, m+1, e, x)
        return -1
    # x_b >= x_m and x_{m+1} <= x_e # shifted, normal
    elif xs[b] >= xs[m] and xs[m+1] <= xs[e]:
        if xs[b] <= x or x <= xs[m]:
            return search(xs, b, m, x)
        if xs[m+1] <= x <= xs[e]:
            return search(xs, m+1, e, x)
        return -1
    else:
        raise Exception()

### Tests

def rotations(seq):
    for n in xrange(0, len(seq)):
        yield seq[n:] + seq[0:n]

def test(n):
    seq   = [2*x for x in xrange(0,n)]
    items = [2*x for x in xrange(0,n)]
    holes = [2*x-1 for x in xrange(0,n+2)]
    runs = 0
    for rseq in rotations(seq):
        for x in items:
            runs += 1
            i = search(rseq, 0, n-1, x)
            assert i >= 0
            assert rseq[i]==x
        for x in holes:
            runs += 1
            i = search(rseq, 0, n-1, x)
            assert i == -1
    return runs

for n in range(1,7):
    runs = test(n)
    print "%s..OK(%s)" % (n, runs)