DAA Lab Assignment 1

Problem statement:

Write a menu driven program to implement binary search (recursive & non-recursive) and

determine the time required to search the element. Repeat the experiment for different values

of n, the number of elements in the list and plot a graph of the time taken versus n. The

elements can be read from a file or can be generated using the random number generator.

Have separate plots when the number was found , and when it was not found.

Implementation in Python:

#import modules required for measuring time, plotting best-fit curve

import numpy as np

import math

import random

import matplotlib.pyplot as plt

from scipy.optimize import curve_fit

from time import perf_counter

def binarySearch(array,target):

low = 0

high = len(array)-1

while low <= high:

mid = (low+high)//2

if target == array[mid]:

return mid

elif target < array[mid]:

high = mid - 1

else:

low = mid + 1

return high+1

#implementation of recursive binary search

def recursiveBinarySearch(array,low,high,target):

if(low > high ):

return high+1

mid = (low+high)//2

if(array[mid]==target):

return mid

elif target < array[mid]:

return recursiveBinarySearch(array,low,mid-1,target)

else:

return recursiveBinarySearch(array,mid+1,high,target)
#helper functions

def testFunction(x,a,b):

return a*np.log2(x) + b

def output(case_no):

input_sizes = []

time_required = []

for i in range(100):

n = 500*(i+1)

array = [random.randint(-25000,25000) for k in range(n)]

array.sort()

start_time = perf_counter()

if case_no==1: #when number is found in array and iterative binary search is used

result = binarySearch(array, array[0]) #array[random.randint(0,len(array))])

elif case_no==2: #when number is not found in array and iterative binary search is used

result = binarySearch(array,random.randint(50000,75000))

elif case_no==3: #when number is found in array and recursive binary search is used

result = recursiveBinarySearch(array,0,len(array)-1, array[0])

else: #when number is not found in array and recursive binary search is used

result = recursiveBinarySearch(array,0,len(array)-1, random.randint(50000,750000))

end_time = perf_counter()
 time_elapsed_microseconds = (end_time - start_time)*(10**6)

input_sizes.append(n)

time_required.append(time_elapsed_microseconds)

plot_graph(input_sizes,time_required)

def plot_graph(input_sizes,time_required):

param,param_cov = curve_fit(testFunction,input_sizes,time_required)

ans = [param[0]*math.log2(input_sizes[i]) + param[1] for i in range(len(input_sizes))]

plt.figure(figsize=(15,6))

plt.plot(input_sizes,time_required,'o',color='red')

plt.plot(input_sizes,ans,'--',color='blue')

plt.xlabel('Input size')

plt.ylabel('Time required(microseconds)')

plt.title('Time required(microseconds) vs. Input size')

plt.show()
Results:

1. Plot of time required by iterative binary search when number is found in the array vs. input sizes

2. Plot of time required by iterative binary search when number is not found vs. input sizes
3. Plot of time required by recursive binary search when number is found vs. input size

4. Plot of time required by recursive binary search when number is not found vs. input size.
Conclusion:

1. The time required by the binary search algorithm to search the number in the worst case (element
at the beginning / end of array) increases logarithmically with the input size. Hence, the time
complexity of the binary search algorithm is O ( log2(N) ) , which can be observed from the
graphs.
2. The results also reveal that the iterative binary search is more time efficient as compared to the
recursive approach. The reason being, recursion involves the overhead of manipulating the call
stack. The time required by the iterative approach to search the number (when number is present
in the array) for a large input size (e.g. 40,000- 50,000) is around 27 microseconds whereas that
for the recursive approach is around 33 microseconds.
3. In terms of space, the iterative approach requires constant amount of space i.e. O(1). However, in
the recursive approach, space complexity may go up to O(log2(N)) because of the overhead of
storing the recursive function calls on the call stack.