Advertisement
Shuva_Dev

Upper Bound & Lower Bound

Nov 29th, 2022
509
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.81 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define endl "\n"
  3. using namespace std;
  4.  
  5. int getLowerBound(vector<int> &v, int x) {
  6.     int L=0, R = v.size(), mid;
  7.  
  8.     while(L < R) {
  9.         mid = L + (R-L)/2;
  10.  
  11.         if(v[mid] < x) {
  12.             L = mid + 1;
  13.         } else {
  14.             R = mid;
  15.         }
  16.     }
  17.     return L;
  18. }
  19.  
  20. /*
  21. int getUpperBound(vector<int> &v, int x) {
  22.     return getLowerBound(v, x+1);
  23. }
  24. */
  25.  
  26. int getUpperBound(vector<int> &v, int x) {
  27.     int L=0, R = v.size(), mid;
  28.  
  29.     while(L < R) {
  30.         mid = L + (R-L)/2;
  31.  
  32.         if(v[mid] <= x) {
  33.             L = mid + 1;
  34.         } else {
  35.             R = mid;
  36.         }
  37.     }
  38.     return L;
  39. }
  40.  
  41. int main() {
  42.  
  43.     vector<int> v = {-5, 0, 0, 2, 3, 5, 7, 8, 8, 10};
  44.    
  45.     cout << getUpperBound(v, 11);
  46.    
  47.    
  48.    
  49.     return 0;
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement