(1-1 DS)Searching

Searching:

  Searching is a process of finding an element within the list of elements stored in any order or randomly.

   Also, searching is more efficient if the data is available in an ordered fashion (sorted order).

   Searching is divided into two categories linear and binary search techniques.

Linear Search:

      The linear search or the Sequential Search is most simple searching method. It does not expect the list to be sorted also Here the element, which is to be searched, is compared with each element of the list one by one. If a match exists, the search is terminated. If the element which is to be searches has no matching element in the list.

  Example Program:

#include<stdio.h>

#include<conio.h>

void main()

{

                int a[MAX];

                int n,I,item;

                int loc=-1;

                printf(“Enter number of elements to insert”);

                scanf(“%d”,&n);

                for(i=0;i<n;i++)

                {

                                printf(“Enter element”);

                                scanf(“%d”,&item);

                                for(i=0;i<n;i++)

                                {

                                                if(item==a[i])

                                                {

                                                                loc=I;

                                                                break;

                                                }

                                                if(loc!=-1)

                                                printf(“The item %d is found at position %d”,Item,loc);

                                                else

                                                printf(“Item is not found in the list”);

                                }

                }

}

Binary Search:

      Binary search is more efficient searching method.  However, the binary search method expects the list to be sorted.  We can apply any one of the sorting method before using the binary search method.

The logic behind this technique is given below:

The given list is divided into two equal halves.  The element to be search is compared with the middle element of the list.  Now three situations may occur:

(a) If middle element match with the key element, then search will end peacefully here.

(b) If middle element is greater than the key element, then element which we are searching is in the first half of the list.

(c) If middle element is less than the Key element, then element which we are searching is in the second half of the list.

  Now the list is searched either in the first half or in the second half as get by the result of conditions (b) & (c) points given above.  This process is repeated till we get the key element or the search fails (i.e., until key does not exit).

Example Program:

#include<stdio.h>

#include<conio.h>

#define MAX 50

void main()

{

                int a[MAX];

                int n, i, eky, first, middle ,last;

                int pos=-1;

                printf("Enter number of elements in array");

                scanf("%d",&n);

                for(i=0;i<n;i++)

                {

                                printf("Enter element");

                                scanf("%d",&a[i]);

                }

                printf("Enter number to search");

                scanf("%d",&key);

                first=0;

                last=n-1;

                while(last>=first)

                {

                                middle=(first+last)/2;

                                if(key>a[middle])

                                first=middle+1;

                                else if(key<a[middle])

                                last=middle-1;

                                else

                                pos=middle;

                                break;

                }

                if(pos!=-1)

                printf("The key %d is found at position %d",key,pos);

                else

                printf("key is not found in the list");

}