fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int upperbound(vector<int> &a, int x)
  5. {
  6. 	int l = 0, r = a.size() - 1;
  7. 	while(l <= r)
  8. 	{
  9. 		int mid = (l + r)/2;
  10. 		if(a[mid] <= x)
  11. 			l = mid;
  12. 		else
  13. 		{
  14. 			if(mid == 0)
  15. 				return 0;
  16. 			else
  17. 			{
  18. 				if(a[mid - 1] <= x)
  19. 					return mid;
  20. 				else
  21. 					r = mid;
  22. 			}
  23. 		}
  24. 	}
  25. 	return a.size();
  26. }
  27.  
  28. int lowerbound(vector<int> &a, int x)
  29. {
  30. 	int l = 0, r = a.size() - 1;
  31. 	while(l <= r)
  32. 	{
  33. 		int mid = (l + r)/2;
  34. 		if(a[mid] >= x)
  35. 			r = mid;
  36. 		else
  37. 		{
  38. 			if(mid == a.size())
  39. 				return a.size();
  40. 			else
  41. 			{
  42. 				if(a[mid + 1] >= x)
  43. 					return mid;
  44. 				else
  45. 					l = mid;
  46. 			}
  47. 		}
  48. 	}
  49. 	return 0;
  50. }
  51.  
  52. int main() 
  53. {
  54. 	int n;  cin>>n;
  55. 	vector<int> ip;
  56. 	for(int i=0; i<n; i++) 
  57. 	{
  58. 		int temp;  cin>>temp;
  59. 		ip.push_back(temp);
  60. 	}
  61. 	int x;  cin>>x;
  62. 	// cout << lowerbound(ip,x) << " " << upperbound(ip,x) << endl;
  63. 	// cout << (first(ip,x)+last(ip,x))/2 << endl;
  64. 	cout << (lowerbound(ip,x)+upperbound(ip,x))/2 << endl;
  65. 	return 0;
  66. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
10
1 2 2 2 2 3 4 5 6 7
2
stdout
copy 
2
https://ideone.com/l15fpR
language:
C++14 (gcc 8.3)
created:
10 days ago
visibility:
public

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!