Reference: Pollice G., Selkow S. and Heineman G. (2016). Algorithms in a Nutshell, 2nd Edition. O' Reilly.
As we saw with Sorting Algorithms, there is no universal best algorithm for every possible use case. The most appropriate search algorithm often depends on the data structure being searched, but also on any a priori knowledge about the data.
Note: Only linear and binary covered in this module.
Search the array a for the target value 7:
Search the array a for the target value 3:
# Searching an element in a list/array in python # can be simply done using \'in\' operator # Example: # if x in arr: # print arr.index(x) # If you want to implement Linear Search in python # Linearly search x in arr[] # If x is present then return its location # else return -1 def search(arr, x): for i in range(len(arr)): if arr[i] == x: return i return -1
Search the array a for the target value 7:
Search the array a for the target value 3:
# Iterative Binary Search Function # It returns location of x in given array arr if present, # else returns -1 def binarySearch(arr, l, r, x): while l <= r: mid = l + (r - l)/2; # Check if x is present at mid if arr[mid] == x: return mid # If x is greater, ignore left half elif arr[mid] < x: l = mid + 1 # If x is smaller, ignore right half else: r = mid - 1 # If we reach here, then the element was not present return -1 # Test array arr = [ 2, 3, 4, 10, 40 ] x = 10 # Function call result = binarySearch(arr, 0, len(arr)-1, x) if result != -1: print "Element is present at index %d" % result else: print "Element is not present in array"
# Python Program for recursive binary search. # Returns index of x in arr if present, else -1 def binarySearch (arr, l, r, x): # Check base case if r >= l: mid = l + (r - l)/2 # If element is present at the middle itself if arr[mid] == x: return mid # If element is smaller than mid, then it can only # be present in left subarray elif arr[mid] > x: return binarySearch(arr, l, mid-1, x) # Else the element can only be present in right subarray else: return binarySearch(arr, mid+1, r, x) else: # Element is not present in the array return -1 # Test array arr = [ 2, 3, 4, 10, 40 ] x = 10 # Function call result = binarySearch(arr, 0, len(arr)-1, x) if result != -1: print "Element is present at index %d" % result else: print "Element is not present in array"
import time #log the start time in seconds start_time = time.time() #call the function you want to be benchmarked #log the start time in seconds end_time = time.time() #calculate the elapsed time time_elapsed = end_time - start_time
import time num_runs = 10 # number of times to test the function results = [] # array to store the results for each test # benchmark the function for r in range(num_runs): # log the start time in seconds start_time = time.time() # call the function that you want to benchmark # log the end time in seconds end_time = time.time() # calculate the elapsed time time_elapsed = end_time - start_time results.append(time_elasped)
from numpy.random import randint from time import time def Bubble_Sort(array): # your sort code sorted=array return sorted def Merge_Sort(array): # your sort code sorted=array return sorted def Counting_Sort(array): # your sort code sorted=array return sorted def Quick_Sort(array): # your sort code sorted=array return sorted def Timsort(array): # your sort code sorted=array return sorted # The actual names of your sort functions in your code somewhere, notice no quotes sort_functions_list = [Bubble_Sort, Merge_Sort, Counting_Sort, Quick_Sort, Timsort] # The prescribed array sizes to use in the benchmarking testst for ArraySize in (100, 250, 500, 750, 1000, 1250, 2500, 3750, 5000, 6250, 7500, 8750, 10000): # create a randowm array of values to use in the tests below testArray = randint(1,ArraySize*2,ArraySize) # iterate throug the list of sort functions to call in the test for sort_type in sort_functions_list: # and test every function ten times for i in range(10): start=time() sort_type(testArray) stop=time() print('{} {} {} {}'.format(sort_type, ArraySize, i, (stop-start)*1000))
Python 3 time documentation: https://docs.python.org/3/library/time.html
Python Date and Time Overview https://www.tutorialspoint.com/python/python_date_time.htm
Discussions of benchmarking issues in Python (advanced material) https://www.peterbe.com/plog/how-to-do-performance-micro-benchmarks-in-python