fork download 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int binarySearch(vector<int> &a, int k, bool strict = false){
  6. 	// if strict is false, returns first index of a, greater than or equal to k
  7. 	// if strict is true, returns first index of a, strctly greater than k
  8. 	int l = 0;
  9. 	int r = a.size();
  10. 	int m = (l+r)/2;
  11. 	while(l<r){
  12. 		if(strict?a[m]<=k:a[m]<k)	l = m+1;
  13. 		else	r = m;
  14. 		m = (l+r)/2;
  15. 	}
  16. 	return m;
  17. }
  18.  
  19. int main() {
  20. 	vector<int> a = {1,1,3,3,3,3,4,4,4,5,5};
  21. 	cout<<"Size of array is "<<binarySearch(a,6)<<endl;
  22. 	cout<<"Count of 3 in array is "<<binarySearch(a,3,true)-binarySearch(a,3)<<endl;
  23. 	cout<<"Index of first 4 is "<<binarySearch(a,4,false)<<endl;
  24. 	cout<<"Index of last 4 is "<<binarySearch(a,4,true)-1<<endl;
  25. 	cout<<"Count of 2 in array is "<<binarySearch(a,2,true)-binarySearch(a,2)<<endl;
  26. 	return 0;
  27. }
Success #stdin #stdout 0s 4484KB
comments ()
stdin 
Standard input is empty
stdout 
Size of array is 11
Count of 3 in array is 4
Index of first 4 is 6
Index of last 4 is 8
Count of 2 in array is 0
https://ideone.com/pJwIFt
Binary Search.
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!