11 Searching – Introduction to Data Structures in C

Chapter 11

Searching

Chapter Outline

11.1 INTRODUCTION

In our day-to-day life there are various applications, in which the process of searching is to be carried. Searching a name of a person from the given list, searching a specific card from the set of cards, etc., are few examples of searching.

A typical example where searching technique is applied is personal telephone diary. This diary is used to store phone / mobile numbers of friends, relatives, etc. For searching the phone number of a person one can directly search the number by using indexing in that diary. Quick search methods are to be adopted to search the data from the heap or large records. Two processes such as searching and sorting are essential for database applications.

In short, searching is a process in which a given record is searched from the set of records. Sorting is a process in which records are arranged in ascending or descending order. A group of field is called record. For example, consider the following structure:

struct employee

{

char *name;

int age;

float height;

} s;

We are familiar with the above declarations and definitions. The object s contains three fields as described in the structure. The database is a collection of such fields. Each record contains the above fields or may vary depending upon the structure defined. The sorting can be done on any one or combination of one or more fields. Suppose, we sort the records based on name. Then, the field name will be the key field. A record is quickly searched in a sorted database. Thus, sorting and searching are very useful concepts of data structure. This chapter aims to provide the information on searching and its techniques.

11.2 SEARCHING

Searching is a technique of finding an element from the given data list or set of the elements like an array, list, or trees. It is a technique to find out an element in a sorted or unsorted list. For example, consider an array of 10 elements. These data elements are stored in successive memory locations. We need to search an element from the array. In the searching operation, assume a particular element n is to be searched. The element n is compared with all the elements in a list starting from the first element of an array till the last element. In other words, the process of searching is continued till the element is found or list is completely exhausted. When the exact match is found then the search process is terminated. In case, no such element exists in the array, the process of searching should be abandoned.

In case the given element is existing in the set of elements or array then the search process is said to be successful as per Fig. 11.1. It means that the given element belongs to the array. The search is said to be unsuccessful if the given element does not exist in the array as per Fig. 11.2. It means that the given element does not belong to the array or collection of the items.

The complexity of any searching method is determined from the number of comparisons performed among the collected elements in order to find the element. The time required for the operation is dependent on the complexity of the operation or algorithm. In other words, the performance of searching algorithm can be measured by counting the comparisons in order to find the given element from the list. There are three cases in which an element can be found.

In the best case, the element is found during the first comparison itself. In the worst case, the element is found only in the last comparison. Whereas in the average case, number of comparisons should be more than comparisons in the best case and less than the worst case.

The searching can be classified into following types:

  1. Linear search (sequential)
  2. Binary search.
11.3 LINEAR (SEQUENTIAL) SEARCH

The linear search is a conventional method of searching data. The linear search is a method of searching a target element in a list sequence. The expected element is to be searched in the entire data structure in a sequential method from starting to last element. Though, it is simple and straightforward, it has serious limitations. It consumes more time and reduces the retrieval rate of the system. The linear or sequential name implies that the items are stored in systematic manner. The linear search can be applied on sorted or unsorted linear data structure.

Fig. 11.1 and 11.2 shows the searching by using the linear search method.

Figure 11.1

Figure 11.2 Unsuccessful search

Example 11.1

Write a program to search an element from the entered numbers. Also, indicate its position in case the element is found or unavailability.

Solution

#include <stdio.h>

#include<conio.h>

main()

{

int sn,arr[10],a;

clrscr();

printf("Enter ten elements:-");

for(a=1;a<=10;a++)

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

printf("Enter the element to be searched:-");

scanf("%d",&sn);

a=1;

while(a<10)

{

if(arr[a]==sn)

{

printf("The number %d is found %d location",sn,a);

break;

}

a++;

}

if(arr[a]!=sn)

printf("The element %d is not found",sn);

}

OUTPUT

Enter ten elements:-12 34 64 23 67 123 346 45 30 19

Enter the element to be searched:-64

The number 64 is found 3 location

Explanation In this program the user enters ten elements by involving an array arr[]. The number, which is to be searched, is initialized with variable sn. By using the for loop ten elements are entered into the arr[]. By using the while loop the number is searched throughout the array and appropriate message is displayed.

Example 11.2

Write a program to search the element from the entered numbers using the pointer.

Solution

#include <stdio.h>

#include<conio.h>

main()

{

int sno,i;

int ar[10],*list;

clrscr();

printf("Enter ten elements:-");

for(i=1;i<=10;i++)

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

printf("Enter the element to be searched:-");

scanf("%d",&sno);

list=&ar[1];

for(i=1;i<=10;i++)

{

if(*list==sno)

  {

    printf("The number %d is found %d location",sno,i);

      break;

  }

list++;

}

if(*list!=sno)

printf("The element %d is not found",sno);

getch();

}

OUTPUT

Enter ten elements:-12 44 23 122 45 67 78 56 65 90

Enter the element to be searched:-67

The number 67 is found 6 location

Explanation In this program *list is a pointer variable which is used to store the address of the first element of the array. Ten elements are entered into the arr[] by using the for loop. First element address is stored into the *list variable. By increasing the address, all elements of the array are accessed. If the match is found then message is displayed on screen.

Example 11.3

Write a program to create a linked list and search a specific element from the linked list.

Solution

include <stdio.h>

# include <conio.h>

# include <malloc.h>

struct link

{

  int num;

  struct link *next;

};

int j;

struct link begin;

void search(struct link*);

void create_list(struct link*);

void show(struct link *);

void create_list(struct link *link)

{

  int n=1,c=1;

  begin.next=NULL;

  link=&begin;

  j=0;

    printf ("\n Input integers (0 to stop) :\n");

  while (n)

  {

  printf("Enter the %d number:-",c);

  scanf ("%d", &n);

  if (n==0) break;

else link->next=(struct link*) malloc(sizeof(struct link));

  link->num=n;

  link=link->next;

  link->next=NULL;

  fflush(stdin);

  c++;

}

}

void search(struct link *link)

{

  int node_num=0;

  int s_node;

  int flag=0;

  link=&begin;

  printf ("\n Enter number to be searched : ");

  scanf ("%d",&s_node);

  if (link==NULL)

  printf ("\n List is empty ");

  while (link)

  {

   if (s_node==link->num)

   {

    printf ("\n search is successful");

    printf ("\n Position of %d from beginning of the list : %d",s_node,node_num+1);

    link=link->next;

    flag=1;

   }

  else

    link=link->next;

    node_num++;

  }

  if (!flag)

  {

    printf ("\n Search is unsuccessful");

    printf ("\n %d does not found in the list", s_node);

  }

}

void show (struct link * link)

{

  link=&begin;

  while(link->next)

  {

    printf(" %d",link->num);

    link=link->next;

  }

}

void main ()

{

struct link *link=(struct link *) malloc (sizeof(struct link));

clrscr();

create_list(link);

  printf ("\n List : ");

  show(link);

  search(link);

}

OUTPUT

Input integers (0 to stop) :

Enter the 1 number:-12

Enter the 2 number:-23

Enter the 3 number:-34

Enter the 4 number:-45

Enter the 5 number:-56

Enter the 6 number:-76

Enter the 7 number:-0

List : 12 23 34 45 56 76

Enter number to be searched : 34

search is successful

Position of 34 from beginning of the list : 3

Explanation In this program, the struct link is used to store linked list. List is created with create () function. The number, which is to be searched, is entered. In the search () function the entered number is compared with the linked list elements. When equal number is found the number along with its position in the linked list is displayed. The show () function is used to display all the linked list elements. Thus, through traversing and comparing elements search process is done.

11.4 BINARY SEARCH

The binary search approach is different from the linear search. Here, search of an element is not passed in sequence as in the case of linear search. Instead, two partitions of lists are made and then the given element is searched. Hence, it creates two parts of the lists known as binary search. Fig. 11.3 illustrates the operation of the binary search.

Binary search is quicker than the linear search. It is an efficient searching technique and works with sorted lists. However, it cannot be applied on unsorted data structure. Before applying binary search, the linear data structure must be sorted in either ascending or descending order. The binary search is unsuccessful if the elements are unordered. The binary search is based on the approach divide-and-conquer. In binary search, the element is compared with the middle element. If the expected element falls before the middle element, the left portion is searched otherwise right portion is searched.

The binary searching method is illustrated in Fig. 11.3.

Figure 11.3 Binary search

Fig. 11.3 represents the operation of binary search. The total elements in the list are 8, and they are shown in the ascending order. In case the key element is less than 5 then searching is done in lower half otherwise in the upper half. The process of searching can be followed from the following Fig. 11.4.

Consider the array of seven elements. The array can be represented in Fig. 11.4(a). The elements of an array are 12, 14, 16, 19, 23, 27, and 31. Assume that we want to search the element 27 from the list of elements. The steps are as follows:

Figure 11.4(a) Array in memory

  1. The element 12 and 31 are at positions first and last, respectively.
  2. Calculate the mid-value which is as

    MID=(FIRST+LAST)/2.

    MID = (0+6)/2.

    MID=3.

  3. The key element 23 is to be compared with the mid-value. If the key is less than the mid then the key element is present in the first half else in the other half; in this case the key is on the right half. Hence, first is equal to middle+1.

    Figure 11.4(b) Calculating the middle at starting

  4. Calculate the middle of the second half.

    MIDDLE=(FIRST+LAST)/2.

    MIDDLE = (4+6)/2

    MIDDLE=5.

  5. Again, the middle divides the second half into the two parts, which is shown in Fig. 11.4(c).
  6. The key element 23 is lesser than the middle 27, hence it is present in the left half (towards the left of 27).

    Figure 11.4(c) Finding element in second half

  7. At last, the middle is calculated as

    MIDDLE = (FIRST + LAST)/2.

    MIDDLE=(4+4)/2.

    MIDDLE=4.

  8. Now, the middle is 4 position and the middle element is 23. The key is searched successfully.

Figure 11.4(d) Result of searching

Based on the above concept an example is illustrated below.

Example 11.4

Write a program to sort an array elements using binary search.

Solution

#include <stdio.h>

#include <conio.h>

main()

{

int items[20], s=0,e,nj,num,mid;

clrscr();

printf ("\n Enter number of elements : ");

scanf ("%d",&n);

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

{

    printf (" Enter element %d : ",1+j);

    scanf ("%d",&items[j]);

}

printf ("\n Enter element to be searched :");

scanf ("%d",&num);

e=n−1;

mid=(s+e)/2;

while (num!=items[mid] && s<=e)

{

if (num>items[mid])

s=mid+1;

else

e=mid−1;

mid=(s+e)/2;

}

if (num==items[mid])

printf ("\n %d found at position %d ",num,++mid);

if (s>e) printf (" %d not found ", num);

getch();

}

OUTPUT

Enter number of elements: 7

Enter element 1: 7

Enter element 2: 13

Enter element 3: 22

Enter element 4: 31

Enter element 5: 45

Enter element 6: 64

Enter element 7: 77

Enter element to be searched: 7

7 found at position 1

Explanation In this program an array items[20] elements is declared. The user is prompted to enter number of elements to be in the list. The numbers are entered through the keyboard. The variable s keeps track of the starting of list and the variable e keeps track of the end. The middle is calculated with the formula mid=(s+e)/2; If the sum of (s+e) is odd number then the result of division operation would be a float value. However, all the operands(s,e) of equation are integers, the float value is converted to lowest integer.

The above explanation is illustrated with the following figure, which is self-explanatory.

Example 11.5

Write a program to demonstrate binary search. Use character array and store 10 names.

Solution

#include<stdio.h>

#include<string.h>

#include<conio.h>

main()

{

int beg=1,mid,end=10,i,flag=0,val;

char name[15][10],fn[15];

clrscr();

printf("Enter 10 names :-\n");

for(i=1;i<11;i++)

   scanf("%s",&name[i]);

printf("\n\tEnter the name to search:-");

scanf("%s",&fn);

mid=(beg+end)/2;

printf("\n\tAt starting beg is %d, mid is %d & end is %d",beg,mid,end);

while((strcmp(fn,name[mid]))!=0 && beg<=end)

{

   val=strcmp(fn,name[mid]);

   if(val>0)

   {

   beg=mid+1;

   mid=(beg+end)/2;

   printf("\n\tmid is %d & beg is %d",mid,beg);

   }

   else

   {

   end=mid−1;

   mid=(beg+end)/2;

   printf("\n\tmid is %d & end is %d",mid,end);

   }

   }

if(strcmp(fn,name[mid])==0){ flag=1; }

  if(flag==1)

printf("\n\tThe name %s is traced successfully",fn);

  else

printf("\n\tThe number %s is not traced",fn);

  getche();

}

OUTPUT

Enter 10 names :-

ashish bhaskar deepak dinesh gajanan ganesh gopal govind raj ramash

Enter the name to search:-deepak

At starting beg is 1, mid is 5 & end is 10

mid is 2 & end is 4

mid is 3 & beg is 3

The name deepak is traced successfully

Enter 10 names :-

ashish bhaskar deepak dinesh gajanan ganesh goval govind raj ramesh

Enter the name to search:-amit

At starting beg is 1, mid is 5 & end is 10

mid is 2 & end is 4

mid is 1 & end is 1

mid is 0 & end is 0

The number amit is not traced

Explanation This program prompts the user to enter ten names.They are stored in the name [15][10], the fn[15] is used to store the name which we want to search. The program uses the binary search to search the entered name. In the search method the user must enter the list of name in ascending order. In this method first the mid is calculated by using beg and end.

11.5 HASHING METHOD

Hashing technique is one of the complex searching techniques. In this section, we consider a class of search techniques whose search time is dependent on the number of entries available in the table. In this method, we fix the position of the key (element) into the table or the file, which is determined by the hash function. The function in which we use this key is known as hashing function.

For example, we want to search a number from the ten numbers of a file. Then, we must find the number throughout this range from the 1st number to 10th number. When we use the key for fixing its position in a table then the number can be searched very easily.

11.6 HASHING FUNCTION

In order to follow the operation of hashing function, consider an array that comprises a list containing some finite number of elements. Each element of it is a key. On performing operations on each key some value is obtained. The key is assigned to the index, which is having the appropriate value. The table is prepared with the keys called a hashing table.

Let us assume the following array that will hold the hash table:

12,22,32,17,19,28, 15,29,16,18,13,11.

Let us use the division method for the following hash table. We divide the key by ‘3’ and the key is placed in the index based on the remainders obtained. The keys having equal remainders are placed in the same index. Any number divided by 3 always returnes 0,1, or 2. Hash table is prepared with three indices such as 0,1,2. All above keys are stored in these three indices as shown in Table 11.1.

Take the first key ‘12’, divide it by ‘3’ .The reminder is ‘0’, hence insert it into the ‘0’ index.

Then, take the next key ‘22’ divide it by the ‘3’, the reminder is ‘1’. Hence, insert the key in to the ‘1’ index.

In the same way divide the key ‘32’ by the 3, its reminder is 2. Place it into the ‘2’ index in the table.

For the remaining elements, the same procedure is to be continued and by knowing reminders the numbers can be placed appropriately in the respective index table.

Table 11.1 explains hashing table.

 

Table 11.1 Hash table

Index Key
0
12, 15, 18
1
22, 19, 28, 16, 13
2
32, 17, 29, 11

In short, the hashing function takes the key, and maps it to some index to the array. In our example, division function has been selected. The programmer can take any other function. This function maps several different keys to the same index. In the above table, key 12,15 and 18 are assigned to the index 0. While keys, 22,19,28,16 and 13 are placed in index 1. Keys 32,17,29 and 11 are in the index 2.

After preparation of the index table, it becomes easier to search the element from the list. One can use any searching method to search the element from the hashing table.

Consider the following program for preparation of an index using divide method.

Example 11.6

Write a program to prepare the hashing table. Enter the elements through the keyboard and map them in index. Use the division function.

Solution

#include<stdio.h>

#include<conio.h>

main()

{

int n[12],i0[12],i1[12],i2[12];

int rem,a=0,b=0,c=0,ij;

clrscr();

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

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

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

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

{

rem=n[i]%3;

if(rem==0)

{

    a++;

    i0[a]=n[i];

      }

else

{

if(rem==1)

{

    b++;

    i1[b]=n[i];

}

else

{

    c++;

    i2[c]=n[i];

}

 }

}

printf("\n\nThe Hashing Table is as follows\n");

printf("--------------------\n");

printf("Index 0 :-");

for(j=1;j<=a;j++)

printf("%5d",i0[j]);

printf("\nIndex 1 :-");

for(j=1;j<=b;j++)

printf("%5d",i1[j]);

printf("\nIndex 2 :-");

for(j=1;j<=c;j++)

printf("%5d",i2[j]);

printf("\n------------------");

}

OUTPUT

Enter the elements of array:-12 22 32 17 19 28 15 29 16 18 13 11

The Hashing Table is as follows

----------------------

Index 0 :- 12 15 18

Index 1 :- 22 19 28 16 13

Index 2 :- 32 17 29 11

----------------------

Explanation In this program the main array ‘n[12]’ is declared having 12 elements. In addition to the above i0[],i1[] and i2[] arrays are initialized for storing the index. These arrays also accommodate 12 elements. In the above program, we calculate the hashing table by using the division method. The keys are divided by 3. Using the mod operation and the reminders are computed, they are placed in the appropriate index.

Some of the hashing methods that are commonly used are stated below.

11.7 DIVISION METHOD

The commonly used hashing method is the division method. In this hashing function, the integer key is divided by some number. The remainder value is taken as the hashing value. This method can be expressed as follows:

H(k)=k(mod x )+1.

In above equation the H(k) is the hashing function. In addition, the k is the key, which is to be used in hashing. The k(mod x) shows the result of division k by x.

In the above equation, the ‘k’ is the key and the ‘x’ is the size of list. We can take any value for the x.

For example, key is 25 and x=10

H(25)=25(mod 10)+1 =5+1=6.

Consider an example to prepare a hashing table and search the prompted number from the hashing table. Each number (key) is divided (mod operation) by 3. No addition of 1 is done after division. It is up to the user how to deal with the problem. The user can perform simply division operation and note down the remainders and place them in appropriate index. As such, there will be 3 indices. The following program illustrates this concept.

Example 11.7

Write a program for division method hashing, and find the given number from the hashing table.

Solution

#include<stdio.h>

#include<conio.h>

main()

{

int n[5],i0[5],i1[5],i2[5];

int num,rem,a=0,b=0,c=0,ij;

clrscr();

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

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

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

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

{

rem=n[i]%3;

if(rem==0)

{

    a++;

    i0[a]=n[i];

}

else

{

if(rem==1)

{

  b++;

  i1[b]=n[i];

}

else

{

    c++;

    i2[c]=n[i];

}

 }

}

printf("\n\nThe Hashing Table is as follows\n");

printf("--------------------\n");

printf("Index 0 :-");

for(j=1;j<=a;j++)

printf("%5d",i0[j]);

printf("\nIndex 1 :-");

for(j=1;j<=b;j++)

printf("%5d",i1[j]);

printf("\nIndex 2 :-");

for(j=1;j<=c;j++)

printf("%5d",i2[j]);

printf("\n-------------------");

printf("\nEnter the key to search:-");

scanf("%d",&num);

rem=num%3;

if(rem==0)

{

    for(j=1;j<=a;j++)

      if(num==i0[j])

        printf("\nThe position of the number is %d in the Index 0"j);

}

if(rem==1)

{

    for(j=1;j<=b;j++)

    if(num==i1[j])

      printf("\nThe position of the number is %d in Index 1"j);

}

if(rem==2)

{

    for(j=1;j<=c;j++)

    if(num==i2[j])

      printf("\nThe position of the number is %d in the Index 2",j);

}

}

OUTPUT

Enter the elements of array:-4 11 5 17 23 12 10 13 6 21

The Hashing Table is as follows

-------------------------

Index 0 :- 12 6 21

Index 1 :- 4 10 13

Index 2 :- 11 5 17 23

-------------------------

Enter the key to search:-23

The position of the number is 4 in the Index 2

Explanation In this program the main array ‘n[]’ is declared. In it, five elements are declared. In addition to the above i0[],i1[] and i2[] arrays are also initialized for storing the index. In the program, we can calculate the hashing table by using the division method. The keys are divided by 3. Using the mod operation, the remainders are calculated and are placed in the appropriate index. The number, which is to be searched, is prompted through keyboard using variable num. The number is divided by 3 and after knowing the reminder; the particular index is searched for searching the element.

Example 11.8

Write a program to prepare hashing table by division method. Use functions and search number from the hashing table.

Solution

#include<stdio.h>

#include<conio.h>

main()

{

void show(int *a,int *nos);

int search(int gno,int *arr,int lim);

int n[5],i0[5],i1[5],i2[5];

int num,rem,a=0,b=0,c=0,i,j;

clrscr();

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

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

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

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

{

rem=n[i]%3;

switch(rem)

{

  case 0: a++; i0[a]=n[i]; break;

  case 1: b++; i1[b]=n[i]; break;

  case 2: c++; i2[c]=n[i]; break;

}

}

printf("\n\nThe Hashing Table is as follows\n");

printf("-------------------\n");

printf("Index 0 :-");

show( &i0[1],&a);

printf("\nIndex 1 :-");

show(&i1[1],&b);

printf("\nIndex 2 :-");

show(&i2[1],&c);

printf("\n-------------------");

printf("\nEnter the key to search:-");

scanf("%d",&num);

rem=num%3;

switch(rem)

{

case 0:

  printf("\nThe position of the number is %d in the Index 0",search(num,&i0[1],a));

  break;

case 1:

  printf("\nThe position of the number is %d in Index 1",search(num,&i1[1],b));

  break;

case 2:

  printf("\nThe position of the number is %d in the Index 2",search(num,&i2[1],c));

  break;

}

}

void show(int *a,int *nos)

{

 int j;

 for(j=1;j<=*nos;j++)

{

printf("%5d",*a);

a++;

}

}

int search(int gno,int *arr,int lim)

{

int j;

for(j=1;j<=lim;j++)

if(gno==*arr)

return j;

else

arr++;

}

OUTPUT

Enter the elements of array:-12 34 65 23 10

The Hashing Table is as follows

-------------------------

Index 0 :- 12

Index 1 :- 34 10

Index 2 :- 65 23

-------------------------

Enter the key to search:-10

The position of the number is 2 in Index 1

Explanation In this program the division hashing method is used for storing the numbers. The i0[],i1[], and i2[] are three arrays, which are used for storing results. The variable a, b, c are used for storing the boundaries of the buckets. The function show() is used to display the elements of a bucket. Function search() is used for searching the given number into the three buckets. In function, show() the two arguments are passed and they are the address of bucket array and address of boundaries. Function search() contains three arguments address of bucket array, value of boundaries, and the given number to search.

11.8 MID-SQUARE METHOD

In mid-square method the key is multiplied with itself and middle digit is chosen as the address of that element in the hashing table. It is defined as follows:

H(k)=(k*k)

For example, if the key is k=12

H(12)=(12*12)=144.

In this example, the key is 12, its square is 144 and its middle digit is 4. Hence, 12 is placed in the hash table in the index 4 as index 4 is the address of 12. Similarly, for other keys the squares are calculated and mid digits are evaluated. Based on the mid digits the keys are placed in the appropriate index. Here, the mid digit obtained can be from 0 to 9. Hence, we may need up to 10 indices starting from index 0 through index 9.

For example, if the key is k=10

H(10)=(10*10)=100. Its middle digit is 0. Hence, number 10 would be placed in index 0. Similarly, the same procedure is adopted for all other numbers and they are placed in different indices based on the mid digit value.

Consider the following number for constricting the hashing table:

12,14,18,20,36,31,27,35,23,59.

 

Table 11.2 Table of key, square and mid

Table 11.3 Hashing table using the mid-square method

A program is prepared for hashing table using the mid-square method.

Example 11.9

Write a program to display the hash table, which is to be prepared by using the mid-square method.

Solution

#include<stdio.h>

#include<conio.h>

main()

{

int msarr[6]={18,21,29,27,12,11},ms1[6],ms2[6],ms3[6],ms4[6];

int a,i,m1,m2,m3,m4,smid;

int squ_mid(int);

void disp(int farr[],int count);

clrscr();

m1=m2=m3=m4=0;

printf("The numbers are as follows :-\n");

for(i=1;i<=7;i++)

printf("\t%d",msarr[i]);

for (a=1;a<7;a++)

{

smid=squ_mid(msarr[a]);

switch (smid)

{

case 1:

{ m1++; ms1[m1]=msarr[a]; break; }

case 2:

{ m2++; ms2[m2]=msarr[a]; break; }

case 3:

{ m3++; ms3[m3]=msarr[a]; break; }

case 4:

{ m4++; ms4[m4]=msarr[a]; break; }

}

}

 printf("\n\nThe Hash Table with Mid-Square method is as follows");

 printf("\n--------------------\n");

 printf("Index 1:-");

 disp(ms1,m1);

 printf("\nIndex 2:-");

 disp(ms2,m2);

 printf("\nIndex 3:-");

 disp(ms3,m3);

 printf("\nIndex 4:-");

 disp(ms4,m4);

 printf("\n-------------------\n");

}

int squ_mid(int ele)

{

  int squ=0,mid,n;

    squ=ele*ele;

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

    {

    mid=squ%10;

    squ=squ/10;

    }

    return mid ;

  }

 void disp(int farr[],int count)

{

int a1;

for(a1=1;a1<=count;a1++)

printf("%5d",farr[a1]);

}

OUTPUT

The numbers are as follows :-

21  29  27  12  11  64  0

The Hash Table with Mid-Square method is as follows

-----------------------

Index 1:-

Index 2:- 27  11

Index 3:-

Index 4:- 21  29  12

-----------------------

Explanation In this program the main array ‘msarr[]’ having six elements are declared. In addition to the above ‘m1[]’, ‘m2[]’, ‘m3[]’ and ‘m4[]’ are initialized. These arrays are initialized for storing the index. Two functions are declared, they are squ_mid(); and dis(). These two functions are initialized for finding the middle digit of the square and display the keys. By using the mod operator, the middle digit of the square number is calculated. After finding the middle digit they are displayed in the hash table.

11.9 FOLDING METHOD

In the folding method, the key is divided into number of parts. The parts, of course, are dependent on the length of the key. All the parts are added together. If the carry results from this operation it is to be ignored and the number what remains behind after ignoring the carry is the address of key. By using this method, we fold the key hence this method is called as folding method.

For example,

1. If key k= 879987

Then, by using this method, we divide it into two parts like 879 and 987. They are added and then carry ignored and the number after ignoring the carry becomes the address of the key.

879 +987 = 1866. Its most significant digit is 1. Hence, after ignoring 1, the number that is left is 866 which is the address of the key.

2. If k=678897678

In this, key is divided into the 3 parts. They are 678, 897 and 678.

By adding, 678+897+678= 2253.

After ignoring last carry 2, the number that is left is 253. Therefore, 253 is the address of the key. Thus, the folding method is useful in converting multiword key into a single word. By applying hashing function, the key can be identified. The reader can develop a program on the topic.

11.10 LENGTH-DEPENDENT METHOD

One more hashing technique used is length dependent method. In this method, the length of the key is measured and the number is placed in the index table appropriately. Here, a simple program is made to search an element from the array. The program is self-explanatory. Length of an array and length of each element can be anything but some finite value can be taken.

Example 11.10

Write a program for searching an element by using the length dependent hash function. Display the hash table and search the element from the table.

Solution

#include<stdio.h>

#include<conio.h>

main()

{

int arr[5],in1[5],in2[5],in3[5],in4[5],in5[5];

int a,i,len,i1,i2,i3,i4,i5,snum;

int length(int);

void disp(int farr[],int count);

void search(int sarr[],int n,int co);

clrscr();

i1=i2=i3=i4=i5=0;

printf("\nEnter the number of the elements:-");

for(i=1;i<=5;i++)

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

for (a=1;a<6;a++)

{

len=length(arr[a]);

printf("\nThe length of %d is:-%d",arr[a],len);

switch (len)

{

case 1:

{ i1++; in1[i1]=arr[a]; break; }

case 2:

{ i2++; in2[i2]=arr[a]; break; }

case 3:

{ i3++; in3[i3]=arr[a]; break; }

case 4:

{ i4++; in4[i4]=arr[a]; break; }

case 5:

{ i5++; in5[i5]=arr[a]; break; }

}

}

printf("\nThe Hash Table is as follows");

printf("\n-------------------\n");

printf("Index 1:-");

disp(in1,i1);

printf("\nIndex 2:-");

disp(in2,i2);

printf("\nIndex 3:-");

disp(in3,i3);

printf("\nIndex 4:-");

disp(in4,i4);

printf("\nIndex 5:-");

disp(in5,i5);

printf("\n--------------------\n");

printf("Enter the number to search;-");

scanf("%d",&snum);

len=length(snum);

switch (len)

{

case 1:

{ search(in1,snum,i1); printf("in Index 1"); break; }

case 2:

{ search(in2,snum,i2); printf("in Index 2"); break; }

case 3:

{ search(in3,snum,i3); printf("in Index 3"); break; }

case 4:

{ search(in4,snum,i4); printf("in Index 4"); break; }

case 5:

{ search(in5,snum,i5); printf("in Index 5"); break; }

}

}

int length(int ele)

{

int c=0,num;

while(ele>0)

{

 if(ele>=10)

 {

  ele=ele/10;

  c++;

 }

else

 {

  c++;

  break;

 }

}

return c ;

}

void disp(int farr[],int count)

{

int a1;

for(a1=1;a1<=count;a1++)

printf("%5d",farr[a1]);

}

void search(int sarr[],int n,int co)

{

int a2;

for (a2=1;a2<=co;a2++)

{

if(n==sarr[a2])

{

printf("The position of the number is %d ",a2);

break;

}

 }

}

OUTPUT

Enter the number of the elements:-1 12 123 12345 1234

The length of 1 is:-1

The length of 12 is:-2

The length of 123 is:-3

The length of 12345 is:-5

The length of 1234 is:-4

The Hash Table is as follows

----------------------

Index 1:-   1

Index 2:-  12

Index 3:- 123

Index 4:- 1234

Index 5:-12345

----------------------

Enter the number to search;-12345

The position of the number is 1 in Index 5

Explanation As usual, the arrays are declared by using arr[], in1[], in2[], in3[], in4[] and in5[] each one having length of 5. By using length(), function length of each key is calculated and the keys are placed in the appropriate index. The number which is to be searched is inputted through the keyboard. Here, snum variable is declared. Its length is calculated by using the length(); and by knowing the length it is searched in the hash table.

11.11 MULTIPLICATIVE HASHING FUNCTION

The name itself indicates that the function is having the multiplication operation in it. The multiplicative hashing function can be written as

H(key)=(b(c*key mod 1))+1.

In this hashing method, the key is multiplied with the number 'c'. The c is used in this function as a constant. After performing the mod of this product with 1 again multiplication operation with the number b is done and 1 is added. The number obtained is the index number for the placing the key.

Mainly, there are two types of searching methods used with hashing function. One is external searching and other is internal search. When the records are bulky then the records can be stored in the file and the file is stored on the disk, tape, etc. The record is outside of the computer memory. On that file the searching operation is to be performed. This searching operation is called as the external searching. Two techniques are used for the external search, one is hashing method and other is tree search method. In another case, when the records are shorter and in less numbers the same can be stored in the computer memory like array, list, etc. In general, the linear searching and binary search are used in the internal searching.

11.12 DIGIT ANALYSIS METHOD

Digit analysis method is the hashing function in which the analysis is done on the whole digits. In this method some digits of some positions of the number are taken out. Then, by making the reverse of the selected digits a value is obtained. The key is transferred to that location. Assume a key 348526917 and just select the digits at the 2, 5 and 7 position. They are as 1,2 and 8. By combining these digits we get a number 128 and after reversing the number have 821. Now, the key is transferred at the address location 821.

Summary
  1. Searching is a technique of finding accurate location of an element in the given item list or set of the elements of an array, list, or trees.
  2. If the given element is present in the collected elements or array then the search process is said to be successful. The search is said to be unsuccessful if the given element does not exist in the array.
  3. The search method in which an element to be searched, is checked in the entire data structure in a sequential way from starting to end is called linear search.
  4. Binary search is quicker than the linear search. However, it cannot be applied on unsorted data structure. This is the precondition. Before applying binary search, the linear data structure must be sorted in either ascending or descending order by using one of the sorted methods.
  5. Hash is one of the complex searching techniques. In this method, the position of the key (element) is fixed into the table or the file, which is determined by the hash function. Division method is explained with a suitable example in this method. Other methods have also been discussed in detail.
Exercises
  1. Answer the following questions:
    1. What is searching? How is the searching process essential for data base applications?
    2. Explain linear and binary search.
    3. Differentiate between linear and binary search.
    4. What are the different searching techniques known to you? Explain one of them in detail with a suitable example.
    5. Distinguish between the external and internal searching.
  2. Select the appropriate option for each of the following questions:
    1. The process of finding a particular record is called
      1. sorting
      2. searching
      3. indexing
      4. none of the above.
    2. In this type of searching the records must be sorted
      1. a. linear search
      2. binary search
      3. selection search
      4. none of the above.
  3. Write the following programs :
    1. Write a program to find the given number in an array of 50 elements. Search how many times a given element exists in the list.
    2. Write a program to demonstrate successful and unsuccessful search. Display appropriate messages.
    3. Write a program to demonstrate binary search. Use character array and store 10 names. Find the given name.
    4. Write a program to search with linear search the given name in string array of 10 names.
  4. What is the output of following programs?
    1. #include <stdio.h>

      #include<conio.h>

      main()

      {

      int n,b=1,a[5];

      clrscr();

      printf("Enter five elements:-");

      while(b<=5)

      { scanf("%d",&a[b]); b++; }

      printf("Enter the element to be searched:-");

      scanf("%d",&00n);

      b=1;

      while(b<=5)

      {

          if(a[b]==n)

      {

      printf("The number %d is found %d

      location",n,b);

      break;

      }

          b++;

      }

      if(a[b]!=n)

          printf("The element %d is not found",n); getch();

      }

       

    2. #include <stdio.h>

      #include<conio.h>

      main()

      {

          int no,j;

          int r[5],*pt;

      clrscr();

      printf("Enter five elements:-");

      for(j=1;j<=5;j++)

      scanf("%d",&r[j]);

      printf("Enter the element to be searched:-");

      scanf("%d",&no);

      pt=&r[1];

      j=1;

      while(j<=5)

      {

      if(*pt==no)

      {

      printf("The number %d is found %d

      location",noj);

      break;

      }

      pt++;

      j++;

      }

      if(*pt!=no)

      printf("The element %d is not found",no);

      getch();

      }

       

    3. #include <stdio.h>

      #include <conio.h>

      main()

      {

      int its[5], st=0,en=4,j,num,mid;

      clrscr();

      for (j=0;j<5;j++)

      {

      printf (" Enter element %d : ",1+j);

      scanf ("%d",&its[j]);

      }

      printf ("\n Enter element to be searched :");

      scanf ("%d",&num);

      mid=(st+en)/2;

      while (num!=its[mid] && st<=en)

      {

      if (num>its[mid])

      st=mid+1;

      else

      en=mid−1;

      mid=(st+en)/2;

      }

      if (num==its[mid])

      printf ("\n %d found at position %d ",

      num,++mid);

      if (st>en)

      printf (" %d not found ", num);

      getch();

      }

       

    4. #include<stdio.h>

      #include<string.h>

      #include<conio.h>

      main()

      {

      int beg=1,mid,end=5,i,flag=0,val;

      char name[5],fn;

      clrscr();

      printf("Enter name:-\n");

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

      scanf("%c",&name[i]);

      printf("\n\tEnter the name to search:-");

      scanf("%s",&fn);

      mid=(beg+end)/2;

      printf("\n\tAt starting beg is %d, mid is %d &

      end is %d",beg,mid,end);

      while((strcmp(fn,name[mid]))!=0 && beg<=end)

      {

      val=strcmp(fn,name[mid]);

      if(val>0)

      {

      beg=mid+1;

      mid=(beg+end)/2;

      printf("\n\tmid is %d & beg is %d",mid,beg);

      }

      else

      {

      end=mid−1;

      mid=(beg+end)/2;

      printf("\n\tmid is %d & end is %d",mid,end);

      }

      }

      if(strcmp(fn,name[mid])==0)

      flag=1;

      if(flag==1)

      printf("\n\tThe name %c is traced

      successfully",fn);

      else

      printf("\n\tThe number %c is not traced",fn);

      getche();

      }

       

    5. #include<stdio.h>

      #include<conio.h>

      main()

      {

      int n[10],bk0[5],bk1[5];

      int rem,a=0,b=0,i;

      clrscr();

      printf("Enter ten numbers:-");

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

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

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

      {

      rem=n[i]%2;

      switch(rem)

      {

      case 0: a++; bk0[a]=n[i];

      break;

      case 1: b++; bk1[b]=n[i];

      break;

      }

      }

      printf("\nIn 0 bkt total number are :-%d",a);

      printf("\nIn 1 bkt total number are :-%d",b);

      }

       

    6. #include<stdio.h>

      #include<conio.h>

      int n[10]={1,2,9,8,4,6,7,5,3,10},b0[5],b1[5];

      main()

      {

      void bucket();

      clrscr();

      bucket();

      }

      void bucket()

      {

      int r,a=0,b=0,i;

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

      {

      r=n[i]%2;

      switch(r)

      {

      case 0: a++; b0[a]=n[i];break;

      case 1: b++; b1[b]=n[i];break;

      }

      }

      printf("\nThe elements of bucket 0 are :-");

      for(i=1;i<=a;i++)

      printf("%3d",b0[i]);

      printf("\nThe elements of bucket 1 are :-");

      for(i=1;i<=b;i++)

      printf("%3d",b1[i]);

      }

       

    7. #include<stdio.h>

      #include<conio.h> int arr[5]={2,9,4,7,10};

      main()

      {

      int no,pos;

      int search(int n);

      clrscr();

      printf("Enter number to search:-");

      scanf("%d",&no);

      pos=search(no);

      if(pos==0)

      printf("\nNumber is not found");

      else

      printf("\n%d number is at %d",no,pos);

      }

      int search(int n)

      {

      int i;

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

      if(n==arr[i])

      return(++i);

      return 0;

      }