Skip to content

Instantly share code, notes, and snippets.

@accessnash
Last active July 9, 2018 20:50
Show Gist options
  • Select an option

  • Save accessnash/bf11ee19cc050b3ab760c811acb99e7d to your computer and use it in GitHub Desktop.

Select an option

Save accessnash/bf11ee19cc050b3ab760c811acb99e7d to your computer and use it in GitHub Desktop.
Binary search algorithm with a measurement of performance in terms of time taken
from time import time
def present(collection, num):
'''finds out if number of our interest is present in collection'''
return num in collection
def binsearch(ordered, num):
'''binary search function to show position of number of our interest in the collection'''
low = 0
high = len(ordered)-1
while low<= high:
mid = round((low + high)/2)
if num == ordered[mid]:
return True
elif num < ordered[mid]:
high = mid - 1
else:
low = mid + 1
return -(low + 1)
def insertqueue(ordered, num):
'''inserts the number of interest in its proper location'''
index = binsearch(ordered, num)
if index < 0:
list(ordered).insert(-(index + 1), num)
return
list(ordered).insert(index, num)
def performance():
'''function measures performance in terms of time of inserting operation'''
n = 1024
while n < 10000000:
sorted = range(n)
now = time()
insertqueue(sorted, n + 1)
done = time()
print(n, (done-now)*1000)
n *= 2
@accessnash

Copy link
Copy Markdown
Author

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment