### Gordon-Freeman's blog

By Gordon-Freeman, history, 3 weeks ago,

If i have a sorted vector like this v={ 5,6,7,8,9,10,11 } how can i get the number of elements that are bigger than x? lets say x is 9 so the number of elements bigger than 9 equals 2 how can i code that?

• +6

 » 3 weeks ago, # | ← Rev. 2 →   +13 Upper bound code#include #include #include int main() { std::vector v = {5, 6, 7, 8, 9, 15, 17}; int x = 9; auto it = std::upper_bound(v.begin(), v.end(), x); int cnt = v.end() - it; std::cout << "Number of elements greater than " << x << " is " << cnt << std::endl; return 0; } 
•  » » 2 weeks ago, # ^ |   0 lol , i did the exact same but when i compile it , it didn't give me any output and the program ended so i submitted the code anyway to ask what's wrong with it , and it got AC!! any idea why did that happen with my compiler? thanks.
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 The below code requires knowledge of binary search. #include using namespace std; // Upper bound: The smallest index such that arr[ind]>N(Strictly greater than). int upperBound(vector arr, int key){ // Here key is the element we want to find upperbound for. int low=0,high=arr.size()-1,ans=arr.size(); while(lowkey) { ans=mid; high=mid-1; } else low=mid+1; } return ans; } int main(){ vector v = {5, 6, 7, 8, 9, 15, 17}; int num=9; int s= upperBound(v,num); cout << "Number of elements greater than " << num << " is " << v.size()-s <
•  » » » 2 weeks ago, # ^ |   +11 where did you submit ? Can you share the group link so I check the problem?
•  » » » » 2 weeks ago, # ^ |   +5 This was the problem 270900251 my code got AC but when i compiled it crashed for some reason that why i was confused
 » 3 weeks ago, # |   0 if the array is sorted you can use binary search to get the result in $O(log n)$ time, also C++ has a prebuilt function named upper_bound which does the same thing, if the array isn't sorted you can sort it first in $O(n log n)$ time and then use binary search or, iterate over the array and calculate it with a for/while loop in $O(n)$
 » 2 weeks ago, # |   0 You can do binary search or use built-in functions in C++ like upper_bound (strictly bigger) or lower_bound (equal or bigger).