Linear search is a very simple search algorithm. In
this type of search, a sequential search is made over all items one by one.
Every item is checked and if a match is found then that particular item is
returned, otherwise the search continues till the end of the data collection.
Linear search algorithm finds given element in a list
of elements with O(n) time complexity where n is total number of elements in
the list. This search process starts comparing of search element with the first
element in the list. If both are matching then results with element found
otherwise search element is compared with next element in the list. If both are
matched, then the result is "element found". Otherwise, repeat the
same with the next element in the list until search element is compared with
last element in the list, if that last element also doesn't match, then the
result is "Element not found in the list". That means, the search
element is compared with element by element in the list.
Linear search is implemented using following steps...
Step 1: Read the search element from the user
Step 2: Compare, the search element with the first
element in the list.
Step 3: If both are matching, then display "Given
element found!!!" and terminate the function
Step 4: If both are not matching, then compare search
element with the next element in the list.
Step 5: Repeat steps 3 and 4 until the search element
is compared with the last element in the list.
Step 6: If the last element in the list is also doesn't
match, then display "Element not found!!!" and terminate the
function.
algorithm(linear search) (linear search given a one dimensional array ‘a’ with ‘n’ elements
and target to be searched .this algorithm find and return the location loc
of item in the array a or set loc=-1 if the search is unsuccessful. here loc is
a local variable.)
1. LOCß
-1[initialize location counter]
2. I ß 1
3. [Search for ITEM]
Repeat while I≤N and A[I]≠ ITEM
I ß I+1 [End of loop]
4. If A[I]=ITEM then[successful]
LOCß I
[End of if structure]
5. Return LOC.
/***************************************************/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 | /*program 1: linear search*/ #include <stdio.h> #include<conio.h> int main() { int array[100], target, i, n; printf("Enter the number of elements in arrayn"); scanf("%d",&n); printf("Enter %d integer(s)n", n); for (i = 0; i < n; i++) scanf("%d", &array[i]); printf("Enter the number to searchn"); scanf("%d", &target); for (i= 0; i< n; i++) { if (array[c] == target) /* if required element found */ { printf("%d is present at location %d.n", target, i+1); break; } } if (i== n) printf("%d is not present in array.n", target); return 0; } /***************************************************/ /* program 2: Linear search for multiple occurrences */ #include <stdio.h> int main() { int array[100], target, i, n, count = 0; printf("Enter the number of elements in arrayn"); scanf("%d", &n); printf("Enter %d numbersn", n); for ( i = 0 ; i < n ; i++ ) scanf("%d", &array[i]); printf("Enter the number to searchn"); scanf("%d", &target); for (i= 0; i< n; i++) { if (array[i] == target) { printf("%d is present at location %d.n", target, i+1); count++; } } if (count == 0) printf("%d is not present in array.n", target); else printf("%d is present %d times in array.n", target, count); return 0; } /***************************************************/ /*program 3: c program for linear search using function*/ #include <stdio.h> #include<conio.h> long linear_search(long [], long, long); int main() { long array[100], search, i, n, position; printf("Input number of elements in arrayn"); scanf("%ld", &n); printf("Input %d numbersn", n); for (c = i; i < n; i++) scanf("%ld", &array[i]); printf("Input number to searchn"); scanf("%ld",&search); position = linear_search(array, n, search); if (position == -1) printf("%d is not present in array.n", search); else printf("%d is present at location %d.n", search, position+1); return 0; } long linear_search(long a[], long n, long find) { long i; for (i = 0 ;i < n ; i++) { if (a[i] == find) Return i; } return -1; } /***************************************************/ //program for linear search using pointers #include<stdio.h> #include<stdlib.h> int c=0; int linearsearch(int *, int,int); int main() { int *a,i,n,value,loc=0; printf("Enter the size of an array: "); scanf("%d",&n); a=(int*)malloc(n*sizeof(int));//allocating memory to array dynamically printf("Enter the elements of the array: "); for(i=0;i<=n-1;i++) { scanf("%d",(a+i)); } printf("Enter the number to be search: "); scanf("%d",&value); loc=linearsearch(a,value,n);// function call if(c==0) printf("The number is not in the listn"); else printf("The number is found at position %dn",loc+1); return 0; } int linearsearch(int *a,int item,int n) { int i; for(i=0;i<=n-1;i++) { if(*(a+i)==item) { c=1; break; } } return i; } |
