Searching algorithms
We often need to find specific data items among millions of other data items. For example, you may want to find a vehicle by searching by its registration number.
Searching are designed to save you from looking through all the data. There are two types of searching algorithm you should be familiar with: linear search and binary search.
Linear/serial search
A linear search can also be known as a serial search. Each item is compared against the item we are searching for.
The search criteria will be entered before the search begins. The search then starts with the first item and compares each item in turn until either a match is found or it reaches the end of the data with no match.
For example: Searching for the number 1 in the below.
The search begins at index 0 and compares the element at index 0 to the search criteria, in this case 1. Does 2 = 1? No. This process of comparison continues until the value and index 2 are compared. Does 1 = 1? Yes. The algorithm can continue and search for other instances until the end of the array, or stop the search.
| Index | [0] | [1] | [2] | [3] | [4] |
| Data | 2 | 5 | 1 | 3 | 4 |
| Index | |
|---|---|
| [0] | |
| [1] | |
| [2] | |
| [3] | |
| [4] |
| Data | |
|---|---|
| 2 | |
| 5 | |
| 1 | |
| 3 | |
| 4 |
This process is better expressed in pseudocode. Either:
for i = 0 to 4 if Numbers[i] == 1 then print("Item found") stopnext iOr:
OUTPUT "Which number would you like to look up?"INPUT user inputs numberSTORE the user's input in the _number variablecounter = 1more_records = TrueWHILE more_records = True: IF counter = _number THEN OUTPUT item found Exit the loopELSE add 1 to counterAdvantages of a linear search
- Will perform fast searches of small to medium lists. With today's powerful computers, small to medium arrays can be searched relatively quickly.
- The list does not need to sorted. Unlike a binary search, linear searching does not require an ordered list.
- Not affected by insertions and deletions. As the linear search does not require the list to be sorted, additional elements can be added and deleted. As other searching algorithms may have to reorder the list after insertions or deletions, this may sometimes mean a linear search will be more efficient.
Disadvantages of a linear search
- Slow searching of large lists. For example, when searching through a database of everyone in the Northern Ireland to find a particular name, it might be necessary to search through 1.8 million names before you found the one you wanted. This speed disadvantage is why other search methods have been developed.
