Binary search is a searching algorithm that works efficiently with a sorted list. The mechanism of binary search can be better understood by an analogy of a telephone directory. When we are searching for a particular name in a directory , we first open the directory from the middle and then decide whether to look for the name in the part of the directory or in the second part of the directory.
Working Of Binary Search-:
Now let us consider how this mechanism is applied to search for a value in a sorted array. Consider an array A[ ] that is declared and initialized as
int A[ ]={ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 }
and the value to be searched is val=9 , the binary search will proceed in following manner
Beg=0 END=10 MID=( 0+10 )/2=5
Now , val=9 and A[ MID ]=5
A[ 5 ]is than val therefore we now search for the value in the second half of the array , so we change the values of BEG and MID
Now BEG=MID+1 =6 END=10 MID=( 6+10 )/2=8
val=9 and A[ 8 ]=8
A[ 8 ] is less than val therefore we now search for the value in the second half of the segment so again we change the values of BEG and MID
Now BEG=MID+1=9 END=10 Mid=( 9+10 )/2=9( here we take only integer part)
Now val=9 A[MID]=9
in this searching method first we find the middle of the array and then check the value if matched then print that location otherwise check if A[MID]<val then go to second half apply the above method and if A[MID]>val then check in first half.
Note-: ( if A[MID]<val BEG=MID+1) and ( if A[MID]>val END=MID-1)
Program Of Binary Search-:
#include <stdio.h>
#include<stdlib.h>
#include<conio.h>
int main()
{
int i, first, last, middle, num, val, array[40];
printf("Enter number of elements in array\n");
scanf("%d", &num);
printf("Enter %d elements in the array \n", num);
for (i = 0; i < num; i++)
{
scanf("%d", &array[i]);
}
printf("Enter value to find\n");
scanf("%d", &val);
first = 0;
last = num - 1;
middle = (first+last)/2;
while (first <= last)
{
if (array[middle] < val)
first = middle + 1;
else if (array[middle] == val)
{
printf("%d found at location %d.\n", val, middle);
break;
}
else
{
last = middle - 1;
}
middle = (first + last)/2;
}
if (first > last)
{
printf("Not found! %d is not present in the list.\n", val);
}
return 0;
}Conclusion-:
I hope this will all of you to understand the concept of Binary Search. all of you can tell me what you want in next post related to data structure in comment section. thanks to all.
Leave a Reply