Binary Search

No more information is required. The name tells everything.

Proof

• Assume the lower bound of the search space is l and upper bound is r.
• Hence the size of search space say n = r-l
• We ask 1 question for this search space i.e. for m = (r-l)/2, at m we ask if given method evaluates true or false
• depending on the result, the new search space either becomes l to m, or m to r
• the size of the new search space = r-m = n/2 or m-l = n/2.
• No matter what the answer is, search space is reduced by a factor of 2
• Hence we have proved that with each successive question we are reducing the search space by a factor of 2
• So in total the search space reduction will look like: n, n/2, n/4, n/8, ... and so on
• final question will be on search space of size 1. At which point the search will terminate
• So for calulation of the total number of questions we can analyse the series above.
• The total number of elements in the above searies (before it reduces to 1), will be the total number of questions asked
• The general ith term of the series can be written as n/(2^i) (0 - indexed)
• from equation 1 = n/(2^i) we can calculate at which i, n reduces to 1, i = log2(n)
• as total number of questions are i+1, Hence total questions asked are congruent to O(log n)

Features

• Both lower bound and upper bound search, by just the switch of a flag.
• Straight forward algorithm, can be reused in any type of scenario which requires a binary search.

V2 features

• flexible usage, any type of binary search can directly use the function. Just need to provide comparison function

Code

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(vector<int> &a, int k, bool strict = false){
	// if strict is false, returns first index of a, greater than or equal to k
	// if strict is true, returns first index of a, strctly greater than k
	int l = 0;
	int r = a.size();
	int m = (l+r)/2;
	while(l<r){
		if(strict?a[m]<=k:a[m]<k)	l = m+1;
		else	r = m;
		m = (l+r)/2;
	}
	return m;
}

int main() {
	vector<int> a = {1,1,3,3,3,3,4,4,4,5,5};
	cout<<"Size of array is "<<binarySearch(a,6)<<endl;
	cout<<"Count of 3 in array is "<<binarySearch(a,3,true)-binarySearch(a,3)<<endl;
	cout<<"Index of first 4 is "<<binarySearch(a,4,false)<<endl;
	cout<<"Index of last 4 is "<<binarySearch(a,4,true)-1<<endl;
	cout<<"Count of 2 in array is "<<binarySearch(a,2,true)-binarySearch(a,2)<<endl;
	return 0;
}

Ideone it!

#include <iostream>
#include <vector>
using namespace std;
struct less_than_k {
	int k;
	less_than_k(int x) : k(x) {}
	bool operator() (int m,vector<int> &v) { return v[m]<k;}
	// this assumes that the above condition is true for the first part of the range [l,r)
	// and it is false for the remaining part the search will return the first element 
	// in the search space which gives false for above condition
	
	// Hence, above condition maps as the follow over the search space
	// t t t t t t t t t t t t t t t t f f f f f f f f f f 
	// function will find the index of ^ element
};
struct less_than_equal_k {
	int k;
	less_than_equal_k(int x) : k(x) {}
	bool operator() (int m,vector<int> &v) { return v[m]<=k;}
};
template <class T, class Comp>
int binarySearch(int l, int r, Comp comp, T& t){
	int m = l+(r-l)/2;
	while(l<r){
		if(comp(m,t))	l = m+1;
		else	r = m;
		m = l+(r-l)/2;
	}
	return m;
}
int binarySearch(vector<int> &a, int k, bool strict = false){
	if(strict)	return binarySearch(0,a.size(),less_than_equal_k(k),a);
	return binarySearch(0,a.size(),less_than_k(k),a);
}
int main() {
	vector<int> a = {1,1,3,3,3,3,4,4,4,5,5};
	cout<<"4th index is less than 2: "<<less_than_k(2)(4,a)<<endl;
	cout<<"6th index is less than equal 4: "<<less_than_equal_k(4)(6,a)<<endl;
	
	cout<<"Size of array is "<<binarySearch(a,6)<<endl;
	cout<<"Count of 3 in array is "<<binarySearch(a,3,true)-binarySearch(a,3)<<endl;
	cout<<"Index of first 4 is "<<binarySearch(a,4,false)<<endl;
	cout<<"Index of last 4 is "<<binarySearch(a,4,true)-1<<endl;
	cout<<"Count of 2 in array is "<<binarySearch(a,2,true)-binarySearch(a,2)<<endl;
	return 0;
}

Ideone it!

Usage

• Usage 1