Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Search Problem

Search means retrieving information from a large amount of stored data using some criteria, e.g. account balances in a banking system, transcripts in a university database, a route in a street directory, or web pages that contain given keywords. The value being looked for is the search key.

The simplest method: store the records in an array and compare the key with each element one by one, from the first to the last.

def sequential_search(L, key):
    for k in range(len(L)):
        if key == L[k]:
            return k               # index of the key
    return -1                      # key not in the array
 
L = [-1, 3, 7, 0, 17]
print(sequential_search(L, 17))    # 4
print(sequential_search(L, 2))     # -1

Time Complexity

The basic operation is the key comparison. The worst case happens when:

  • the key is in the last position of the array, or
  • the key is not in the array at all

Either way all elements are checked, so the worst case is . The best case is one comparison when the key is the first element.

When to Use It

Points:

  • works on unsorted data and on linked lists, where there is no direct access by index
  • simple, but slow for large
  • if the data is sorted, binary search needs only comparisons