Thursday, May 10, 2012

What is linear search!!

Linear Search  is the one of the basic search algorithm used in computer science. This is also called brute force searching algorithm, because, it just starts the searching each element in the array from starting position until key found or end of the array. Here the advantage is with this algorithm  is that array of elements can be any order where as in binary search the elements should be in sorted order. This searching algorithm will be useful if the no. of elements in the array are less or small.

Algorithm for linear search:

1. Get the element key which needs to be search in the array
2. Get the array of the elements in which key needs to be search
3. take the elements from position zero  in the array
4. compare the element with key  matches stops the process
5. if not matches proceed for the next element until end of the array
6. repeat steps from 3 to 6

Time Complexity of Linear Search: The best case for this searching algorithm is O(1). Because , we may get the searchin key in the first position itself. And the worst case of linear search algorithm is O(n). Because we may get the searching key  in the last position in the array or we may not get the key  element in the array. Because of this complexity, its not advisable to use this searching algorithm if the no. of eleaments in the array more(probabley more than 100).
Program of linear search in C:
int linear_search(int arr[], int key, int max_pos)
{
    int pos;
    for(pos=0;pos<max_pos;pos++)
    {
        if(arr[pos]==key)
            return pos;
    }
    return -1;
}
main()
{
    int arr[10],i,pos,key;
    int startIndex=0;
    int endIndex=9;
    printf("enter the elements in array in sorted orderd only\n");
    for(i=0;i<10;i++)
    {
        scanf("%d",&arr[i]);
    }
    printf("enter the element to be searched\n");
    scanf("%d",&key);
    pos = linear_search(arr,key,endIndex);
    if(pos!=-1)
        printf("element %d find at position %d\n",key,pos);
    else
        printf("element not in the array\n");
}

Results:
enter the elements in array in sorted orderd only

234
45
56
78
90
12
23
123
534
765
enter the element to be searched
534
element 534 find at position 8



enter the elements in array in sorted orderd only
234
34
45
56
67
89
90
12
23
34
enter the element to be searched
1234
element not in the array

No comments:

Popular Posts