Binary Search:
Binary Search is a searching technique where the sorted array is divided into two parts for each search.
Let's consider a array
arr[] = {2,4,7,8,9,18,20}
We want to find the element 20
Key = 20
Indexing of this array:
arr[0] = 2
arr[1] = 4
arr[2] = 7
arr[3] = 8
arr[4] = 9
arr[5] = 18
arr[6] = 20
Now we will first calculate the mid element
mid = (starting index + ending index)/2
Here, in this case
mid = (0+6)/2
mid = 3
Therefore, arr[mid] = arr[3] = 8
Now , if the key is greater than the mid element then the starting index would be
(mid+1), and if the key is less than the mid element then ending index would be
(mid-1).
Here, in this case the key is 20 which is greater than mid element that's why starting index would be (mid+1) = 4. Then it will again search the key element from 9 to 20.
As well as 20 is present so, it will return the index of that key element.
Code For Binary Search:
#include<stdio.h>
int binarySearch (int arr[], int n, int key)
{
int b=0;
int e=n;
while(b<=e)
{
int mid=(b+e)/2;
if(arr[mid]==key)
{
return mid;
}
else if(arr[mid]<key)
{
b=mid+1;
}
else{
e=mid-1;
}
}
return-1;
}
int main()
{
int arr[]={2,4,7,8,9,13,20};
int n=7;
int key=6;
int ans=binarySearch (arr,n-1,key);
printf("Printing array:\n");
for(int i=0;i<n;i++)
{
printf("%d\n",arr[i]);
}
printf ("\n");
printf ("Key to be searched: %d\n", key);
printf ("\n");
if(ans==-1)
{
printf ("key not found!");
}
else{
printf("Found at position %d\n", ans);
}
return 0;
}
Output:
Printing array:
2
4
7
8
9
13
20
Key to be searched: 6
key not found!
Printing array:
2
4
7
8
9
13
20
Key to be searched: 20
Found at position 6