Linear Search(Sequential Search)

 Linear Search

1. It is also Called as "Sequential Search".
2. This is simplest method.
3. It can be applied to sequential storage structure like files, array, or linked list.

• Advantages of Linear Search

1. It is very simple method.
2. It does not require the data to be sorted.
3. It does not require any additional data structure.

• Disadvanatges of Linear Search

1. If  'n' is very large, this method is very in efficient and slow.
2. It's worst case complexity O(n).

• Analysis of sequential search

Best Case: -The best case  occurs when the key is found at the first position i.e at index 0.

                  -The best case time complesxity Ω(1).

 
Worst Case:-The case occurs when the key is not found in array.

                    -The worst case time complexity O(n).

Average Case:-Average comparisons = n(n+1)/2n = (n+1)/2.

                        -The average case time complexity of this method is O(n).

CODE

👇

1. #include <stdio.h>
2. int linear_search(int a[10], int n, int key);
3. int main()
4. {
5.         int a[10], key, n, pos;
6.         printf("INPUT NUMBER OF ELEMENT IN ARRAY:");
7.         scanf("%d", &n);
8.         printf("ENTER %d NUMBERS:\n", n);
9.         for(int i=0; i<n; i++)
10.             scanf("%d", &a[i]);
11.         printf("ENTER NUMBER TO SEARCH:\n");
12.         scanf("%d", &key);
13.         pos=linear_search(a, n, key);
14.         if(pos == -1)
15.             printf("%d IS NOT PRESENT IN ARRAY!!\n", key);
16.         else
17.             printf("%d IS PRESENT IN ARRAY\n", key);
18.   return 0;  
19. }
20. 
    
21. int linear_search(int a[10], int n, int key)
22. {
23.         int i;
24.         for(i=0; i<n; i++)
25.         {
26.             if(a[i]==key)
27.             return 1;
28.         }
29.     return -1;
30. }

👉Execute👈

//Output

/*

1]

INPUT NUMBER OF ELEMENT IN ARRAY:5

ENTER 5 NUMBERS:

1

3

5

7

9

ENTER NUMBER TO SEARCH:

5

5 IS PRESENT IN ARRAY

2]

INPUT NUMBER OF ELEMENT IN ARRAY:5

ENTER 5 NUMBERS:

1

3

5

7

9

ENTER NUMBER TO SEARCH:

6

6 IS NOT PRESENT IN ARRAY!!

*/

                                                                               //ThE ProFessoR