Skip to content
This repository has been archived by the owner. It is now read-only.
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
36 lines (27 sloc) 783 Bytes
"""
Binary Search
-------------
Recursively partitions the list until the `key` is found.
Time Complexity: O(lg n)
Psuedo Code: http://en.wikipedia.org/wiki/Binary_search
"""
def search(seq, key):
"""
Takes a list of integers and searches if the `key` is contained within
the list.
:param seq: A list of integers
:param key: The integer to be searched for
:rtype: The index of where the `key` is located in the list. If `key` is
not found then False is returned.
"""
lo = 0
hi = len(seq) - 1
while hi >= lo:
mid = lo + (hi - lo) // 2
if seq[mid] < key:
lo = mid + 1
elif seq[mid] > key:
hi = mid - 1
else:
return mid
return False
You can’t perform that action at this time.