mehedi1

Lowerbound, upperbound when element is existed or non-existed

Dec 5th, 2020
950
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 lower_bound(int arr[], int n, int X) {
  5.     int l = 0;
  6.     int r = n;
  7.  
  8.     // Till low is less than high
  9.     while (l < r) {
  10.         int mid = (l+r)/2;
  11.  
  12.         // If X is less than or equal
  13.         // to arr[mid], then find in
  14.         // left subarray
  15.         if (X <= arr[mid]) {
  16.             r = mid;
  17.         }
  18.  
  19.         // If X is greater arr[mid]
  20.         // then find in right subarray
  21.         else {
  22.             l = mid + 1;
  23.         }
  24.     }
  25.  
  26.     // Return the lower_bound index
  27.     return l;
  28. }
  29.  
  30. int upper_bound(int arr[], int n, int X) {
  31.     int l = 0;
  32.     int r = n;
  33.  
  34.     // Till low is less than high
  35.     while (l < r) {
  36.         // Find the middle index
  37.         int mid = (l+r)/2;
  38.  
  39.         // If X is greater than or equal
  40.         // to arr[mid] then find
  41.         // in right subarray
  42.         if (X >= arr[mid]) {
  43.             l = mid + 1;
  44.         }
  45.  
  46.         // If X is less than arr[mid]
  47.         // then find in left subarray
  48.         else {
  49.             r = mid;
  50.         }
  51.     }
  52.  
  53.     // Return the upper_bound index
  54.     return l;
  55. }
  56.  
  57. // Function to implement lower_bound
  58. // and upper_bound of X
  59. void printBound(int arr[], int n, int X) {
  60.     int idx;
  61.  
  62.     // If lower_bound doesn't exists
  63.     if (lower_bound(arr, n, X) == n) {
  64.         printf("Lower bound doesn't exist");
  65.     }
  66.     else {
  67.         // Find lower_bound
  68.         idx = lower_bound(arr, n, X);
  69.         printf("Lower bound of %d is %d at index % d\n ", X, arr[idx], idx);
  70.     }
  71.  
  72.     // If upper_bound doesn't exists
  73.     if (upper_bound(arr, n, X) == n) {
  74.         printf("Upper bound doesn't exist");
  75.     }
  76.     else {
  77.         // Find upper_bound
  78.         idx = upper_bound(arr, n, X);
  79.         printf("Upper bound of %d is %d at index % d\n ", X, arr[idx], idx);
  80.     }
  81. }
  82.  
  83. int main() {
  84.     int arr[] = { 4, 6, 10, 12, 18, 20 };
  85.     int n = sizeof(arr) / sizeof(arr[0]);
  86.  
  87.     // Element whose lower bound and
  88.     // upper bound to be found
  89.     int X = 6;
  90.  
  91.     // Function Call
  92.     printBound(arr, n, X);
  93.  
  94.     printBound(arr, n, 7);
  95.     return 0;
  96. }
  97.  
  98.  
  99. /*
  100. eikhane amader r=n newa lage karon output jokhon n asbe tokhon bujhte parobo je array te lowerbound/ upperbound exist kore nah
  101. */
RAW Paste Data