Concept of Linear Search

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

linear-search-ex-1

 
Try Now – Data Structure MCQs
Practice Now – Data structure:Searching Sorting MCQ Based Online Test