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; }