Advertisement
shabbyheart

Lower bound

Mar 17th, 2019
222
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.34 KB | None | 0 0
  1. ///Finding lowerbound by two method
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. /*int l_bound(int arr[],int n,int k)
  5. {
  6.     int lo=0,hi=n-1,ans=-1;
  7.     while(lo<=hi)
  8.     {
  9.         int mid=(lo+hi+1)/2;
  10.         if(arr[mid]==k){
  11.             ans=mid;
  12.             hi=mid-1;
  13.         }
  14.         else if(k<arr[mid])
  15.             hi=mid-1;
  16.         else
  17.             lo=mid+1;
  18.     }
  19.     return ans;
  20. }
  21. int main()
  22. {
  23.     int arr[7]={1,2,2,2,3,4,5};
  24.     cout<<"lower bound of 2 is: ";
  25.     cout<<l_bound(arr,7,2);
  26. }*/
  27.  
  28. vector<int>vec;
  29. int lo_bound(int k)
  30. {
  31.     int low_range=0,high_range=vec.size()-1,ans=-1;
  32.     while(low_range<=high_range)
  33.     {
  34.         int mid_range=(low_range+high_range)/2;
  35.         if(vec[mid_range]==k)
  36.         {
  37.             ans=mid_range;
  38.             high_range=mid_range-1;
  39.         }
  40.         else if(k<vec[mid_range])
  41.         {
  42.             high_range=mid_range-1;
  43.         }
  44.         else
  45.             low_range=mid_range+1;
  46.     }
  47.     return ans;
  48.  
  49. }
  50. int main()
  51. {
  52.     int n;
  53.     cout<<"Enter how many element"<<endl;
  54.     cin>>n;
  55.     cout<<"Enter values are:"<<endl;
  56.     while(n!=0)
  57.     {
  58.         int value;
  59.         cin>>value;
  60.         vec.push_back(value);
  61.         n--;
  62.     }
  63.     cout<<"which value lower bound you want to find: ";
  64.     int k;
  65.     cin>>k;
  66.     cout<<"Lower bound is: "<<lo_bound(k);
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement