Binary Search works on sorted array, unlike linear search we saw here. It works on the concept of divide and conquer. It performs better than linear search.

Algorithm for binary search is stated below

- To search for the key element, we divide the array into two parts.
- Then we compare key element to the middle item.
- If key element is more than middle element, we search the element in next part of the array.
- Else, we search the element in the first half of the array.
- We repeat the steps 3 and 4 till we find the element.
- Else we give the output as -1, to represent that the element is not present.

For example, we need to find 6, from the elements {1,2,3,4,5,6,7,8,9}.

The implementation of the same algorithm is stated below in C++ program.

```
#include<iostream>
using namespace std;
int binary_search(int a[],int key,int n){
int lo = 0;
int hi = n-1;
int mid;
while(lo<=hi){
mid = (lo+hi)/2;
if(a[mid]==key) return mid;
if(key<a[mid]) hi = mid-1;
else lo = mid+1;
}
return -1;
}
int main(){
int a[]={1,2,3,4,5,6,7,8,9};
int z = binary_search(a,6,sizeof(a)/sizeof(int));
if(z!=-1){
cout<<"Element is at "<<z;
}
else {
cout<<"Element is not present";
}
return 0;
}
```