Skip to content

Instantly share code, notes, and snippets.

@MShel
Last active April 18, 2017 17:03
Show Gist options
  • Save MShel/022ddbf3fa16eb2a47dd3afe0780c8a4 to your computer and use it in GitHub Desktop.
Save MShel/022ddbf3fa16eb2a47dd3afe0780c8a4 to your computer and use it in GitHub Desktop.
Simple Recursive python binary search
import random
def binarySearch(sortedArray: list, searchFor, prevMiddle = 0) ->int:
middle = int(len(sortedArray)/2)
if(sortedArray[middle] == searchFor):
return prevMiddle + middle
elif(sortedArray[middle] < searchFor):
#should keep a track of left index of array
prevMiddle += middle
return binarySearch(sortedArray[middle:], searchFor, prevMiddle)
else:
return binarySearch(sortedArray[:middle], searchFor, prevMiddle)
test = [1,2,3,4,5,6,7,8,9,10,11]
lookingFor = random.choice(test)
result = binarySearch(test, lookingFor)
print('result key = ' + str(result))
assert test[result] == lookingFor, "The search is broken"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment