Example to illustrate Binary search
consider an array[10]
Data: 10 18 19 20 25 30 49 57 64 72
Array: a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
search no = 49
Iteration 1: start = 0
end= 9
middle = (start+end)/2;
= 0 + 9 / 2
= 4.5
= rounded 4 i.e a[4]=25
Iteration 2: search no 49 > 25
start = middle + 1 = 4 + 1 = 5
end= 9
middle = (start+end)/2;
= 5 + 9 / 2
= 7 i.e a[7]= 57
Iteration 3: search no 49 < 57
start = 5
end= middle - 1 = 7 - 1 = 6
middle = (start+end)/2;
= 5 + 6 / 2
= 5.5
= rounded 5 i.e a[5]= 30
Iteration 4: search no 49 < 30
start = middle + 1 = 5 + 1 = 6
end= 6
middle = (start+end)/2;
= 6 + 6 / 2
= 6 i.e a[6]= 49
Iteration 5: search no 49 is equal to middle no 49 i.e 49 = 49
stop.
Program :
// Program to illustrate Binary Search
#include <stdio.h>
int main()
{
int array[100],start,end, middle , search , flag, i, n;
printf("Enter number of elements in array\n");
scanf("%d", &n);
printf("Enter %d integer(s)\n", n);
for (i = 0; i < n; i++)
{
scanf("%d", &array[i]);
}
printf("\n Array elements are :");
for (i = 0; i < n; i++)
{
printf("\n Address.> :%p --> Array : array[%d] Data : %d Location : %d", &array[i],i,array[i],i+1);
}
printf("\nEnter a number to search :");
scanf("%d", &search);
start = 0;
end = n - 1;
while (start <= end)
{
middle = (start+end)/2;
if (search < array[middle])
end = middle - 1;
else if (search > array[middle])
start = middle + 1;
else if(search == array[middle])
{
printf("element %d found at location %d.\n", search, middle+1);
flag=1;
break;
}
}
if (flag==0)
printf("Not found! %d isn't present in the list.\n", search);
return 0;
}
output:
