A Python function that parses through a sorted list (descending order) using a binary search method to determine if an element is present. Best case O(1), worst case O(log n), and uses very low memory.

Usage

The code can be stress-tested as such:

arr = range(10000)
del arr[10]

start = time.time()
for x in range(-1, len(arr)+2):
    binary_search(arr, x)
print "Took", str(round(float(time.time() - start), 6)), "seconds to search for each element of a", len(arr), "item list"

However, in practice, you would simply do something like:

containsOne = binary_search(someArray, 1)

The function can only be run on a sorted array containing integers. To implement it for a custom user function, you would have to have an additional function, to wrap each side of the less-than and equal-to statements, that would return an integer. Regardless of elements, the array MUST be sorted.

Code

def binary_search(arr, element):
    lower = 0;
    upper = len(arr);
    while (lower < upper):
        n = (lower + upper)/2;
        if (element == arr[n]):
            return True;
        elif (element < arr[n]):
            upper = n;
        else:
            lower = n + 1;
    return False;