## General Introduction:

Binary Search is the more efficient searching technique compared to Linear Search. The binary search technique only takes 0(log n) times for n number of elements in an array.

However, it only works if the elements in an array are in sorted order( ascending or descending order).

## Searching Technique:

Searching Technique:

- The middle of the array of items is calculated as m=(floor(l+r)/2) where l is the initial index of the array, r is the last index of the array.
- The searched item is compared with the element in the middle of the array.
- If a[m]==key, then the search is successful where the key is the searched element.
- If a[m]<key, then the searched element exists in the second half of the array.
- If a[m]>key, then the searched element exists in the first half of the array and is, therefore, is to be searched there only.

## Example:

a[]={5,10,15,20,25,30,35,40,45,50}

Element to be searched( key)= 15.

Here, n=9(counting from 0)

l=0, r=9

Therefore, m=(floor(0+9)/2)=4.

a[m]=a[4]=25 (counting from 0).

Here, a[m]>key: so the element is to be searched in the first half of the array.

The first half of the array : a[]={5,10,15,20}

Element to be searched =15.

Here, n=3(counting from 0)

l=0, r=3

Therefore, m=(floor(0+3)/2)=1

a[m]=a[1]=10 (counting from 0).

Here, a[m]<key: so the element is to be searched is exist in the second half of the array.

The second half of the array: a[]={15,20}

Element to be searched =15.

Here, n=1(counting from 0)

l=0, r=1

Therefore, m=(floor(0+1)/2)=0

a[m]=a[0]=15(counting from 0).

Here, a[m]==key: so the element is to be searched is found in the array.

## Code in C:

```
#include<stdio.h>
#include<conio.h>
int binary_search(int[],int,int,int);
int main()
{
int a[20];
int n;
int key;
int i;
int value; /* to check if the element exist or not*/
printf("How many items you want to insert in the array:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\nEnter %dth item: ",i+1);
scanf("%d",&a[i]);
}
printf("\nEnter the item you want to binary search:");
scanf("%d",&key);
value=binary_search(a,0,n-1,key);
if(value==1)
{
printf("Element %d exists in the array.",key);
}
else
{
printf("Element %d does not exist in the array.",key);
}
getch();
return(0);
}
int binary_search(int a[],int l,int r,int key)
{
int m;
if(l<=r)
{
m=(l+r)/2;
if(a[m]==key)
{
return 1;
}
else if(a[m]<key)
{
return binary_search(a,m+1,r,key);
}
else
{
return binary_search(a,l,m-1,key);
}
}
else
{
return -1;
}
}
```

## Outputs in C:

Do comment if you are confused in any steps.

Also Read: C Program to Find Gcd of Two Numbers using Iterative Euclid’s Algorithm