Programming constructs - CCEASearching an array

Linear search

As discussed in the digital design principles revision guide, arrays can be accessed serially, i.e. one element at a time. The linear search algorithm can be implemented in Python as follows:

fruit = ["Banana", "Apple", "Pear", "Lemon"] # Array to be searched
found = False # A flag to break the searching loop
i = 0 # a counter to control the loop search = input("Enter Search Criteria:") while not found and i < len(fruit): # if the counter is less than the number # of elements in the array and has not been found if fruit[i] == search: # if the element in the array matches the search criteria print(str(search) + "was found at position" + str(i)) found = True # break out of the loop i = i + 1
if not found: print(str(search) + "was not found")

Outputs:

Enter Search Criteria: Lemon
Lemon was found at position 3

or

Enter Search Criteria: Melon
Melon was not found

A linear search uses a flag (in this case found variable) to stop the search, a counter variable is used to search through the elements (in this case i) and the counter is incremented with each iteration.

Binary search

Binary search is a divide and conquer algorithm which requires the initial array to be sorted before searching.

In a binary search, we first find the midpoint and compare it to the value we are searching for. If it doesn't match, then if the item we are looking for is less than the one found we perform a binary search on the left half of the list; otherwise we perform a binary search on the right half.

This is repeated in the relevant half of the list each time the variable is not found we reduce the portion of the list searched by half.

def binarySearch(alist, item): #search function accepts 2 parameters first = 0 #first and last variable to uses as limits of the search last = len(alist) - 1 found = False while first <= last and not found: midpoint = (first + last) //2 # finds the midpoint between the first and last elements in the subset if alist[midpoint] == item: found = True else: if item < alist[midpoint]: #if the item is lower than the midpoint last = midpoint - 1 else: first = midpoint + 1 #if the item is larger than the midpoint return found
testList = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(binarySearch(testList, 3))
print(binarySearch(testList, 13))

Outputs:

False
True

Although a binary search is a little harder to program, it is far more efficient than a linear search.

For example, an array with 1000 elements would mean 10 probes using binary search. A linear search of the same array could mean up to 1000 probes (in the worst case scenario).