#!/usr/bin/python

#  A[0..n-1] be an array. For 0 <= lo <= hi <= n-1 
#  A[lo..hi] is the slice of the array A that needs to be searched 
#  mid is the value returned -- mid = n if x is not in the array.

def binsearch (A, x):
    n = len (A)
    lo = 0
    hi = n
    mid = (lo + hi)//2
    # INV: {  ordered A /\ (forall i: 0<= i < lo: x <> A[i]) /\
    #         (forall j: hi < j < n: x <> A[j]) /\ 
    #         0<= lo <= mid <= hi <= n /\ 2*mid <= lo+hi <= 2*mid+1
    #      }
    # Notice that mid = lo if hi = lo or hi = lo+1 and 
    # lo < mid < hi holds only if hi-lo > 1
    while (hi-lo > 1) and x <> A[mid]:
        if x < A[mid]:
            hi = mid -1
        elif x > A[mid]:
            lo = mid + 1
        mid = (lo + hi)//2
    if x == A[mid]:
        return mid
    else:
        return None


# try it
A = [-24, -24, -12, -12, 0, 0, 1, 20, 45, 123]
print (binsearch (A, 0))
print (binsearch (A, -24))
print (binsearch (A, 123))
print (binsearch (A, 100))
print (binsearch (A, ~25))
print (binsearch (A, 124))