# 619480
import time
from random import *

def main():
lst = []
result, length = 0, 500000
while result <= 0.50:
for i in range(length):
lst.append(randint(1, length))
value = randint(1, length)
t0 = time.clock()
linearSearch(value, lst)
result = time.clock() - t0
print("This LINEAR SEARCH took {0:4.2f}seconds with a length of".format(result), length)
lst.sort()
t0 = time.clock()
binarySearch(value, lst)
result = time.clock() - t0
print("This BINARY SEARCH took {0:4.2f}seconds with a length of".format(result), length, "\n")
lst = []
length = length + 500000

def binarySearch(value, lst):
low, high = 0, len(lst) - 1
while low <= high:
mid = (low + high) // 2
item = lst[mid]
if value == item:
return mid
elif value < item:
high = mid - 1
else:
low = mid + 1
return -1

def linearSearch(value, lst):
for i in range(len(lst)):
if value == lst[i]:
return i
return -1

main()

I'm trying to time the two algorithms at the bottom using the clock function. The linearSearch get's timed fine, it gives me a value, however, when it comes to timing the binarySearch, it always reports 0.00. Why? What am I doing wrong? :s

Seconds resolution is too coarse for binary search, move to milliseconds:

def main():
lst = []
result, length = 0, 500000
while result <= 0.50:
for i in range(length):
lst.append(randint(1, length))
value = randint(1, length)
t0 = time.clock()
linearSearch(value, lst)
result = (time.clock() - t0) * 1000 …

All 3 Replies

Seconds resolution is too coarse for binary search, move to milliseconds:

def main():
lst = []
result, length = 0, 500000
while result <= 0.50:
for i in range(length):
lst.append(randint(1, length))
value = randint(1, length)
t0 = time.clock()
linearSearch(value, lst)
result = (time.clock() - t0) * 1000
print("This LINEAR SEARCH took {0:4.2f} milliseconds with a length of".format(result), length)
lst.sort()
t0 = time.clock()
binarySearch(value, lst)
result = (time.clock() - t0) * 1000
print("This BINARY SEARCH took {0:4.2f} milliseconds with a length of".format(result), length, "\n")
lst = []
length = length + 500000

You might also find it handy to use timing decorator like this (just write @timing at line before definition of the function you want to time)

import time
from functools import update_wrapper

def timestr(t):
return ( ("%i min %.3f s" % divmod(t, 60)) if t > 60
else  (("%.3f s" % t) if t > 1
else "%.3f ms" % (t * 1000) ) )

def timing(func):
def wrapper(*arg, **kwargs):
t1 = time.clock()
res = func(*arg, **kwargs)
t2 = time.clock()
print('%s took %s' % (func.__name__, timestr(t2-t1)))
return res

return update_wrapper(wrapper, func)

or you might start to use the timeit module

I recommend also to take look at http://paulbutler.org/archives/python-debugging-with-decorators/ or similar decorators from net to make your life easier.

Here is a version with timeit

# 619480
import time
from random import *
from timeit import Timer
timer = Timer("binarySearch(Spam.value, Spam.lst)", "from __main__ import Spam, binarySearch")
class Spam:
pass

def main():
lst = []
result, length = 0, 500000
while result <= 0.50 and length < 10**7:
for i in range(length):
lst.append(randint(1, length))
value = randint(1, length)
t0 = time.clock()
linearSearch(value, lst)
result = time.clock() - t0
print("This LINEAR SEARCH took {0:4.2f}seconds with a length of".format(result), length)
lst.sort()
number = 1000
Spam.value, Spam.lst = value, lst
result = timer.timeit(number)
#t0 = time.clock()
#binarySearch(value, lst)
#result = time.clock() - t0
print("This BINARY SEARCH took {0:4.2e}seconds with a length of".format(result/number), length, "\n")
lst = []
length = length + 500000

def binarySearch(value, lst):
low, high = 0, len(lst) - 1
while low <= high:
mid = (low + high) // 2
item = lst[mid]
if value == item:
return mid
elif value < item:
high = mid - 1
else:
low = mid + 1
return -1

def linearSearch(value, lst):
for i in range(len(lst)):
if value == lst[i]:
return i
return -1

main()

""" my output --->
('This LINEAR SEARCH took 0.03seconds with a length of', 500000)
('This BINARY SEARCH took 6.54e-06seconds with a length of', 500000, '\n')
('This LINEAR SEARCH took 0.07seconds with a length of', 1000000)
('This BINARY SEARCH took 5.83e-06seconds with a length of', 1000000, '\n')
('This LINEAR SEARCH took 0.24seconds with a length of', 1500000)
('This BINARY SEARCH took 7.55e-06seconds with a length of', 1500000, '\n')
('This LINEAR SEARCH took 0.59seconds with a length of', 2000000)
...
"""

Brilliant thank you guys!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.