A binary search algorithm is an algorithm used to search an already sorted list for an element in the list.

The method is analogous to guessing the answer to a number guessing game, where you are provided with a range of numbers and will guess the number in the mind of the host. The host may respond with "higher [number]", "lower [number]" and "yes" (meaning the guess is correct).

The algorithm runs in O(log2 n) time.

## Pseudocode

This inputs a list `arr(0 to n-1)` and outputs the index of the item if it is found, otherwise -1.

### Recursive

```binary_search(arr, item)
binary_search(arr, item, 0, n-1)

binary_search(arr, item, low, high)
if high < low
return -1
middle = (low + high) / 2
if A at mid > value
return binary_search(arr, item, low, mid-1)
else if A at mid < value
return binary_search(arr, mid+1, high)
else
return mid
```

### Non-recursive

```binary_search(arr, item)
low = 0
high = n-1
// you may choose whether or not to initialize mid here
while not high < low  // can be rephrased as low >= high
mid = (low + high) / 2
if arr at mid > item
high = mid - 1
else if arr at mid < item
low = mid + 1
else
return mid
return -1```

## Algorithm

Here is the C++ Code

```#include <bits/stdc++.h>
using namespace std;
```
```bool binarysearch(vector<int> v, int t)
{
int low = 0, mid, high = v.size()-1;
while(low<=high)
{
mid = low + (high-low)/2;
if (t == v[mid])
{
cout<<mid<<endl;
return true;
}
else if(t < v[mid])
{
high = mid-1;
}
else
low=mid+1;
}
cout<<"-1";
return false;
}
```
```int main()
{
vector<int> v;
vector<int>::iterator it;
int n,p;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>p;
v.push_back(p);
}
sort(v.begin(),v.end());
cin>>p;
binarysearch(v,p)
return 0;
}
```