C program to implement binary search

What is binary search?

As the name implies binary search divides the array into two equal parts and proceeds only with one of these parts, which may contain the element that is searched. Binary search requires that the array contains elements, either in ascending order or in descending order.

Explanation of the program

The program reads the size of the array and stores it in the variable n. Next the elements are read into the array a[] in ascending order. Then the element to be searched is read into the variable i. The variable l and u stores the lower bound and upper bound values for the array. Initially lower bound is 0 and upper bound is n. These values change each time as the array size is reduced. 

(l+u)/2 gives the middle index of the array, it is stored in the variable m. Next the value stored in this location is compared with the element to be searched. If it equals, the element is found and we closes the loop. If i is less than  a[m], the elements after a[m] is dropped from the array otherwise elements before a[m] is dropped from the array. The search is proceeded with the remaining part of the array until the element is found or all elements are searched. 

Example

Suppose the array size is 5 and contains the following elements.

10   14   17   20   23

We need to search for the element 14

Here,

l=0 (Lower bound) & u=5 (Upper bound)

m=(l+u)/2=2 (value after decimal is omitted)

a[m]= a[2]= 17

14 is less than 17

so we now consider only the elements before 17, ie 10 & 14.

Now, u=0 and l=2

m=(l+u)/2=1

a[m]= a[1]= 14

14 equals 14, so we have found the element.

Program

#include<stdio.h>

#include<conio.h>

void main()

{

int a[25],n,m,l,u,f=0,i,j;

printf("Enter the size of the array: ");

scanf("%d",&n);

printf("Enter the elements in sorted order: ");

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

{

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

}

printf("Enter the item to be searched for: ");

scanf("%d",&i);

l=0;

u=n;

while(l<=u)

{

m=(l+u)/2;

if(a[m]==i)

{

printf("\n\nItem found at position %d",m+1);

f=1;

break;

}

else if(a[m]>i)

{

u=m-1;

}

else

{

l=m+1;

}}

if(f==0)

printf("\n\nItem not found in the array");

getch();

}

Output

C program for binary search