fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Class to compute upper bound
  5. class UpperBoundFinder {
  6. public:
  7.     // Function to find the upper bound using binary search
  8.     int upperBound(vector<int> &arr, int x, int n) {
  9.         int low = 0, high = n - 1;
  10.         int ans = n;  // Default answer if x is >= all elements
  11.  
  12.         while (low <= high) {
  13.             int mid = (low + high) / 2;
  14.  
  15.             if (arr[mid] > x) {
  16.                 ans = mid;        // Potential answer found
  17.                 high = mid - 1;   // Try to find smaller valid index on the left
  18.             } else {
  19.                 low = mid + 1;    // Move right if mid is <= x
  20.             }
  21.         }
  22.         return ans;  // Index of the first element > x
  23.     }
  24. };
  25.  
  26. int main() {
  27.     vector<int> arr = {3, 5, 8, 9, 15, 19};  // Sorted input array
  28.     int n = arr.size();                     // Size of the array
  29.     int x = 18;                              // Target value
  30.  
  31.     UpperBoundFinder finder;               // Create object
  32.     int ind = finder.upperBound(arr, x, n);  // Call method
  33.  
  34.     cout << "The upper bound is the index: " << ind << "\n";  // Output result
  35.     return 0;
  36. }
  37.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The upper bound is the index: 5
https://ideone.com/WVqVrE
language:
C++ (gcc 8.3)
created:
10 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!