Reference no: EM132107409

Programming Exercise .

In Python, the use the binary search functions given(recursive and iterative). Generate a random ordered list of integers and do a benchmark analysis. What are your results ? Explain the results.

Recursive:

def binarySearch(alist, item):
if len(alist) == 0:
return False
else:
midpoint = len(alist)//2
if alist[midpoint]==item:
return True
else:
if item<alist[midpoint]:
return binarySearch(alist[:midpoint],item)
else:
return binarySearch(alist[midpoint+1:],item)

iterative:

def binarySearch(alist, item):
first = 0
last = len(alist)-1
found = False

while first<=last and not found:
midpoint = (first + last)//2
if alist[midpoint] == item:
found = True
else:
if item < alist[midpoint]:
last = midpoint-1
else:
first = midpoint+1

return found