Binary Search
The prerequisite for using binary search is that the list must be a sorted one. We compare the element to be searched with the element placed approximately in the middle of the list.
If a match is found, the search terminates successfully. Otherwise, we continue the search for the key in a similar manner either in the upper half or the lower half. If the elements of the list are arranged in ascending order, and the key is less than the element in the middle of the list, the search is continued in the lower half. If the elements of the list are arranged in descending order, and the key is greater than the element in the middle of the list, the search is continued in the upper half of the list. The procedure for the binary search is given in the following program.
Example
#include <stdio.h>
#define MAX 10
void bsearch(int list[],int n,int element)
{
int l,u,m, flag = 0;
l = 0;
u = n-1;
while(l <= u)
{
m = (l+u)/2;
if( list[m] == element)
{
printf(" The element whose value is %d is present at position %d in list\n", element,m);
flag =1;
break;
}
else
if(list[m] < element)
l = m+1;
else
u = m-1;
}
if( flag == 0)
printf("The element whose value is %d is not present in the list\n", element);
}
void readlist(int list[],int n)
{
int i;
printf("Enter the elements\n");
for(i=0;i<n;i++)
scanf("%d",&list[i]);
}
void printlist(int list[],int n)
{
int i;
printf("The elements of the list are: \n");
for(i=0;i<n;i++)
printf("%d\t",list[i]);
}
int main()
{
int list[MAX], n, element;
printf("Enter the number of elements in the list max = 10\n");
scanf("%d",&n);
readlist(list,n);
printf("\nThe list before sorting is:\n");
printlist(list,n);
printf("\nEnter the element to be searched\n");
scanf("%d",&element);
bsearch(list,n,element);
getchar();
return 0;
}
In the binary search, the number of comparisons required to search one element in the list is no more than log2n, where n is the size of the list. Therefore, the binary search algorithm has a time complexity of O(n *( log2n.).)
