mehedi1

Lowerbound, upperbound when element is existed

Dec 5th, 2020
577
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. int bslowerbound(vector<int> v,int x) {
  5.     int l=0, r=v.size()-1;
  6.     int idx=-1;
  7.     while(l<=r) {
  8.         int mid=(l+r)/2;
  9.         if(v[mid]>=x){
  10.             if(v[mid]==x) idx=mid;
  11.             r=mid-1;
  12.         }
  13.         else if(v[mid]<x) l=mid+1;
  14.     }
  15.     return idx;
  16. }
  17. int bsupperbound(vector<int> v,int x) {
  18.     int l=0, r=v.size()-1;
  19.     int idx=-1;
  20.     while(l<=r) {
  21.         int mid=(l+r)/2;
  22.         if(v[mid]<=x){
  23.             if(v[mid]==x) idx=mid;
  24.             l=mid+1;
  25.         }
  26.         else if(v[mid]>x) r=mid-1;
  27.     }
  28.     return idx;
  29. }
  30. int main() {
  31.     vector<int>vec;
  32.     int target, n;
  33.     scanf("%d",&n);
  34.     for(int i=0; i<n; i++)
  35.     {
  36.         int val;
  37.         scanf("%d",&val);
  38.         vec.push_back(val);
  39.     }
  40.     scanf("%d",&target);
  41.  
  42.     cout<<bslowerbound(vec,target)<<endl;
  43.     cout<<bsupperbound(vec,target)<<endl;
  44.     return 0;
  45. }
  46.  
  47. /*
  48. input jodi hoy eirokom:
  49. 8
  50. 10 10 10 20 20 20 30 30
  51. 20
  52.  
  53. tahole lowerbound er dibe: 3 (3rd index)
  54. upperbound dibe: 6 (6th index)
  55. ------------------------------------
  56.  
  57. ar eirokom input dile:
  58. 8
  59. 10 10 10 20 20 20 30 30
  60. 21
  61.  
  62. lowerbound, upperbound duitar e output: -1
  63. (karon eikhane array te 21 exist kore nah)
  64. */
RAW Paste Data