Question

Draw a single graph in Python showing the performance of both algorithms against the number of elements (100,000). Consider the worst case scenario. In the graph we want to see: labeling of the axes, a legend, a title and the graphs for both linear and binary search, again correctly labeled. Explain what you see.

Answer 1

#------- plotting.py -----------

import random
import time
import matplotlib.pyplot as plt

#linear search method that returns the
#index of num in array if not found return -1
def linear_search(array,num):
   for i in range(len(array)):
       if(array[i] == num):
           return i
   return -1
#binary search method that returns the
#index of num in array if not found return -1
def binary_search(array,num):
   low = 0
   high = len(array)-1
   while(low<high):
       mid = low + (high-low)//2
      
       if(array[mid] == num):
           return mid
       elif(array[mid] < num):
           low = mid + 1
       else:
           high = mid - 1
   return -1

#create array of given size
size = 100000
array = [x for x in range(size)]
#worst case scenario for finding is giving a number that is not there.
#in both search methods it will be the worst scenario.

#linear search times
linear_times = []
#binary search times
binary_times = []
row = [x for x in range(10)]
for i in range(10):
   print("\n------- Test -",i+1,"------")
   findOne = random.randint(100000,120000)
   print("\nSearching:",findOne,"using Linear Search")
   #start time for linear search
   st_time = time.time()
   linear_search(array,findOne)
   end_time = time.time() - st_time
   linear_times.append(end_time)
  
   #cal time for binary search
   findTwo = random.randint(-100,-1)
   print("\nSearching:",findTwo,"using Binary Search Search")
   b_st_time = time.time()
   binary_search(array,findTwo)
   b_end_time = time.time() - b_st_time
  
   binary_times.append(b_end_time)

#plot linear times
plt.plot(row,linear_times,"r",label="Linear Search Time")
#plot binary times
plt.plot(row,binary_times,"g",label="Binary Search Time")
#set legends
plt.legend(loc="upper left")
#set axes labels
plt.xlabel("Number of Test runs")
plt.ylabel("Time Taken")
plt.title("Performance of Search Algorithms for Size: " + str(size))
plt.show()

OBSERVATION:

It is clearly observed that linear search takes much more time than the binary search for a given array of size 100000,