Testing and Evaluating Search Algorithms

Testing a search means running it on targets you have chosen on purpose, not on one lucky value. Good test data shows whether the search finds targets in different places, copes when the target is missing, and how much work each search takes.

Test data to choose

Pick targets at the start, middle and end of the collection, plus a target that is not present. Each one takes the algorithm down a different path. A linear search needs one comparison to find the first item, several to reach a middle item, and every item to reach the last one or to prove a target is absent, so the same algorithm can look fast or slow depending on where the target sits.

Use both sorted and unsorted versions of a collection. A linear search should work on either, while a binary search only gives correct results when the data is sorted. Running binary search on an unsorted list is a useful test because it shows the algorithm giving wrong results — the data is not in the order it needs. If you plan to sort the data first, test that route too.

Reasoning about fitness for purpose

Being fit for purpose means doing the job well enough for the situation, so you judge a search by logical reasoning from the facts. Ask how big the collection is, whether it is already sorted, where the target is likely to sit, and what sorting would cost. Sorting takes many comparisons and several passes through the list, and some sorting algorithms need extra memory, so it is only worth doing if the collection will be searched again and again.

Situation	Fitter choice	Reason
12 club members, unsorted, one lookup	Linear search	Few comparisons, and sorting would cost more than the search
60,000 customer records, unsorted, searched all day	Sort once, then binary search	The sorting cost is paid once, then each search discards half of the remaining records
Collection that cannot be rearranged	Linear search	Binary search relies on the items being in order

Counting comparisons turns "it feels fast" into evidence. This program runs one linear search for each of four test targets and shows the result, the index and the number of comparisons made:

def linear_search(items, target):
    compares = 0
    for i in range(len(items)):
        compares = compares + 1
        if items[i] == target:
            print("Found at index:")
            print(i)
            print("Comparisons made:")
            print(compares)
            return
    print("Not found")
    print("Comparisons made:")
    print(compares)

lockers = [210, 214, 218, 222, 226, 230, 234]
for t in [210, 222, 234, 250]:
    linear_search(lockers, t)

Output:

Found at index:
0
Comparisons made:
1
Found at index:
3
Comparisons made:
4
Found at index:
6
Comparisons made:
7
Not found
Comparisons made:
7

Test data to choose

Reasoning about fitness for purpose

Practise this