In case of large arrays, the method of comparing every array element with key as described above is rather inefficient. However, if an array is a sorted one, the search process can be considerably shortened by using binary search method. For the application of binary search the array should be first sorted.
Once the array has been sorted, the following procedure must be used:
(i) Determine the number of elements in the array.
(ii) Divide the array into two halves.
(iii) Compare the middle element of the array with the key. If match occurs the search is successful.
(iv) lf it does not match, find that half of the array which contains the key.
(v) Change the limits of search to the half of the array that contains the key.
(vi) Again divide the chosen half (in which the key lies) into two halves.
(vii) Repeat Steps (iii) to (v).
(viii) Continue the process of dividing the array till the value is located.
For large, ordered arrays this method is very efficient. Program illustrates the binary search method. If the value is not contained in the array, then the program gives output that the element is not present in the array.
Illustrates binary search of an array for a value
#include <stdio.h>
main()
{
int key , Size, Start, End, Mid ;
int Array[] = {11,22,23,44,54,65,73,89,93,107,156,178,211};
printf("Write the number you want to find:");
scanf("%d", &key);
Size= sizeof (Array) I sizeof(int);
Start = 0;
End = Size -1
while (Start <= End)
{
if (Start ==End && Array [End] != key)
{
printf("The number is not in the array.\n");
break;
}
Mid= (Start+ End)/2;
if ( Array[Mid] == key)
{
printf( "Value found. It is Array [%d]\n", Mid);
break;
}
else if(Array[Mid] > key)
End = Mid-1;
else
Start = Mid+l;
}
return 0;
}
Dinesh Thakur holds an B.C.A, MCSE, MCDBA, CCNA, CCNP, A+, SCJP certifications. Dinesh authors the hugely popular Computer Notes blog. Where he writes how-to guides around Computer fundamental , computer software, Computer programming, and web apps. For any type of query or something that you think is missing, please feel free to Contact us.
Related Articles
Basic Courses
Advance Courses