This is the simplest of all searching techniques. In this technique, an ordered or unordered list will be searched one by one from the beginning until the desired element is found. If the desired element is found in the list then the search is successful otherwise unsuccessful.
Suppose there are ‘n’ elements organized sequentially on a List. The number of comparisons required to retrieve an element from the list, purely depends on where the element is stored in the list. If it is the first element, one comparison will do; if it is second element two comparisons are necessary and so on. On an average you need [(n+1)/2] comparison’s to search an element. If search is not successful, you would need ’n’ comparisons.
The time complexity of linear search is O(n).
Example 1:
Suppose we have the following unsorted list: 45, 39, 8, 54, 77, 38, 24, 16, 4, 7, 9, 20
If we are searching for:
45, we’ll look at 1 element before success
39, we’ll look at 2 elements before success
8, we’ll look at 3 elements before success
54, we’ll look at 4 elements before success
77, we’ll look at 5 elements before success
38 we’ll look at 6 elements before success
24, we’ll look at 7 elements before success
16, we’ll look at 8 elements before success
4, we’ll look at 9 elements before success
7, we’ll look at 10 elements before success
9, we’ll look at 11 elements before success
20, we’ll look at 12 elements before success
For any element not in the list, we’ll look at 12 elements before failure
