Binary Search Algorithm

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(log₂ 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;
}