Question

Design an application that has an array of at least 20 integers. It should call a module that uses the sequential search algorithm to locate one of the values. The module should keep a count of the number of comparisons it makes until it finds the value. Then the program should call another module that uses the binary search algorithm to locate the same value. It should also keep a count of the number of comparisons it makes. Display these values on the screen.

Answer 1

Answer:

1. def sequenceSearch(myList, target):
2.    count = 0
4.    for x in myList:
5.        count += 1
6.        if(x == target):
7.            return count  
8.    
9.    return -1
11. def binarySearch(myList, target):
12.    minIndex = 0
13.    maxIndex = len(myList) - 1
14.    count = 0
16.    while(maxIndex >= minIndex):
17.        middleIndex = minIndex + (maxIndex - minIndex)//2
18.        count += 1
20.        if(target < myList[middleIndex]):
21.            maxIndex = middleIndex - 1
22.        elif(target > myList[middleIndex]):
23.            minIndex = middleIndex + 1
24.        else:
25.            return count  
27.    return -1
31. myList = [4, 7, 9, 12, 15, 19, 21, 40, 57, 80, 91, 111, 123, 127, 145, 167, 178, 180, 210, 222]
32. print(sequenceSearch(myList, 210))
33. print(binarySearch(myList, 210))

Explanation:

Firstly, create a sequential search function that will take two parameter, list and target number (Line 1). In the function, create a counter variable, count and initialize it with zero (Line 2). Next create a for loop to start the sequential search from the first element of list and keep tracking of count (Line 4 -7). If target is found in the list, return the count (Line 7) otherwise return -1.

Next, create another function for binary search that will take the same input parameters as sequential search function (Line 11). In the binarySearch function, use the similar counter variable, count to track the number of searching (Line 14).  Next, use a while loop to implement the binary search algorithm that will keep comparing target against the list element in middle index (Line 20 - 25). If target is smaller than middle value adjust the maxIndex by having middleIndex -1. If target bigger than the middle value, set the minIndex to middleIndex - 1. Otherwise it will return the count. If the target is not found, return -1 (Line 27).

In the main program, create a sample list with 20 elements and then test the sequenceSearch and binarySearch function ny using the sample list and target = 210 as arguments. We shall get the output: 19 4