Finding Data Item - Searching

FINDING DATA ITEM - SEARCHING

Suppose we have a collection of data items of some specific type and we wish to determine if a particular data item is in that collection. The particular data item we want to find is called the key and our task is to search the records in the data base to find one which matches the key.

The first decision we must make is how to represent the collection of data items. We know that the data structure, which could hold a collection of similar data items called the array. So we can consider our database of integer values to be stored in an array.

Example: Search an array for an index where the key is located, if key is not present, print a message. Repeat until an end of file is entered for the key.

In this task, we choose to return the index where the key is located because this index will allow us to retrieve the entire record in the case where our array is part of a database. The simplest approach to determine if a key is present in an array is to make an exhaustive search of the array. Start with the first element, if the key matches, we are done; otherwise move on to the next element and compare the key, and so on.

We simply traverse the array in sequence from the first element to the last as shown in figure below. Each element is compared to the key. If the key is found in the array, the corresponding array index is returned. If the item is not found in the array, an invalid index, say ‒1, is returned. This type of search is called Sequential Search or Linear Search because we sequentially examine the elements of the array. In the worst case, the number of elements that must be compared with the key is linearly proportional to the size of the array.

1. Linear Search or Sequential Search

This is the simplest known technique for searching an array for a particular record or data element. In LINEAR search, we start with the first available element, that is the element that comes first. If this is the required element then our search is over, else we take up the second element and see if this is the element that we need. If this too is not the required element, then we pick up the third element. This process of considering the next record will go on till we find the required element or all the elements in the table are exhausted.

Illustration to find the 62 from the given list.

/* Program to find the specified element from the array using Linear searching */

#include <stdio.h>

#include<conio.h>

main()

{

/* Local definitions */

int i,j,k, no,a[100], f=1;.

char c='y',ch;

/* Statements */

clrscr();

while(c == 'y'||c== 'Y')

{

          printf("\nEnter the size of sorting");

          scanf("%d", &no);

          printf("\nEnter the elements of the array");

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

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

          printf("\nEnter the element to be searched");

          scanf("%d", &k);

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

          {

                    if(k==a[i])

                     {

                    printf("\nElement %d is in the position %d",k,i+1);

                    f=2;

                    break;

                    } /* if */

          } /* for */

          if(f==1)

          printf("\nThe entered element is not in the array");

          printf("\nIf you want to continue y/n");

          ch=getch();

          c=ch;

} /* while */

getch();

} /* main */

OUTPUT

Enter the size of sorting 5

Enter the elements of the array 3 2 1 4 5

Enter the element to be searched 4

Element 4 is in the position 4

If you want to continue y/n

EXPLANATION : The above program reads the entered number of element through for loop. The program checks the specified element and position in the array according to the user entered number. Then the program prints the specified element and their position.

2. Binary Search

Binary Search is simpler and faster than the Linear Search. Binary search is called so because, on each search the array to be searched is divided into two parts, one of which is ignored as it will not contain the required element. One essential condition for the binary search is that the array which is to be searched should be arranged in order. This is absolute for this method to work.

In Binary search, we start, by taking a look at the approximate middle element. If the number of elements in an array is odd, then the middle element is considered. In case the table has even number of elements, then the last element of the first half is taken into consideration

Then, we compare the middle element with the one we wish to search in an array. If the value of middle element is greater than the element to be searched then we discard the first half of the array and start all over again by taking the second half of the array. If the value of middle element is smaller than the element to be searched, then we discard the second half of the array.

We keep on looking for the middle element of the table and keep on discarding either the first or second half of the array depending on the result of the comparison of the middle element and the element to be searched, till we find the required element when the array cannot be further subdivided.

 /* Program to find the specified element from array using Binary search */

#include <stdio.h>

#include <conio.h>

void main()

{

int a[100],i,no,l,h,m,t,f=1; /* Local definitions */

/* Statements */

clrscr();

printf("Enter the size of the array \n");

scanf("%d", &no);

printf("Enter the elements in ascending order");

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

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

printf("Enter the elements to be searched");

scanf("%d", &t);

l=0;

h=no‒1;

while(l<=h)

{

       m=(1+h)/2;

       if(t<a[m])

       h=m‒1;

       else if(t>a[m])

       l=m+1;

       else

       {

       printf("\n Entered %d is in position %d",t,m+1);

       f=2;

       break;

       }/* if else */

}  /* while */

if(f==1)

printf("\n Entered element is not in the array");

getch();

} /* main */

OUTPUT

Enter the size of the array 5

Enter the elements in ascending order 1 3 4 5 6

Enter the elements to be seareched 3

Entered 3 is in position 2

EXPLANATION: The above program gets the last number no from the terminal then reads the ascending order number through for loop. The while loop statement executes the block of statement then prints the position of the entered number as output. This program refers the binary searching.