Блог пользователя Hussam_Jdid

Автор Hussam_Jdid, история, 2 года назад, По-английски

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
  • Проголосовать: не нравится

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +13 Проголосовать: не нравится

Upper bound

code
»
2 года назад, скрыть # |
 
Проголосовать: нравится 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)$$$