Tuesday, 28 February 2017

Linear Search in one dimensional Array

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",&amp;n);
    printf("Enter %d  integer(s)n", n);
    for (i = 0; i &lt; n; i++)
    scanf("%d", &amp;array[i]);
    printf("Enter the number to searchn");
    scanf("%d", &amp;target);
    for (i= 0; i&lt; 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", &amp;n);
    printf("Enter %d numbersn", n);
    for ( i = 0 ; i &lt; n ; i++ )
    scanf("%d", &amp;array[i]);
    printf("Enter the number to searchn");
    scanf("%d", &amp;target);
    for (i= 0; i&lt; 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", &amp;n);
    printf("Input %d numbersn", n);
    for (c = i; i &lt; n; i++)
    scanf("%ld", &amp;array[i]);
    printf("Input number to searchn");
    scanf("%ld",&amp;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 &lt; 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",&amp;n);
    a=(int*)malloc(n*sizeof(int));//allocating  memory to array dynamically
    printf("Enter the elements of the array: ");
    for(i=0;i&lt;=n-1;i++)
    {
        scanf("%d",(a+i));
    }
    
    printf("Enter the number to be search: ");
    scanf("%d",&amp;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&lt;=n-1;i++)
    {
        if(*(a+i)==item)
        {
            c=1;
            break;
        }
    }
    return i;
    
}
Posted by at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)