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.
Sequential (Linear) Search
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)) # -1Time 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