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.
The code can be stress-tested as such:
arr = range(10000) del arr 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.
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;