Problem Statement

Given a sorted array of nums and an integer x, write a program to find the upper bound of x. The upper bound algorithm finds the first or the smallest index in a sorted array where the value at that index is greater than a given key i.e. x.

If no such index is found, return the size of the array.

Examples

Example 1:

Input: n = 4, nums = [1, 2, 2, 3], x = 2
Output: 3

Explanation: Index 3 (3) is the smallest index such that nums[3] > x

Example 2:

Input: n = 5, nums = [3, 5, 8, 15, 19], x = 9
Output: 3

Explanation: Index 3 (15) is the smallest index such that nums[3] > x

Example 3:

Input: n = 5, nums = [3, 5, 8, 15, 19], x = 3
Output: 1

Explanation: Index 1 (5) is the smallest index such that nums[1] > x

Different Approaches

1️⃣ Linear Search

Intuition:

Imagine you're a concert organizer with a sorted list of ticket prices. A customer wants to know the first ticket price that is more expensive than a certain amount they can afford. This helps them see which tickets are out of their budget.

For example, have the following sorted list of ticket prices: [10, 20, 30, 40, 50, 60, 70, 80].

A customer can afford to pay up to Rs35. You want to find the first ticket price that exceeds Rs35.

Hence in order to find the first price greater than Rs35, you can go through the list one by one from the start until you find a price that's more than Rs35. This method is linear search approach to find the solution to this problem.

Approach:

1. To find the upper bound of a given target value in an array, iterate through each element of the array.
2. Compare each element with the given target value. Continue this comparison until you find an element that is greater than the target.
3. The smallest index where the current element is greater than the target, will be the upper bound of the target element in the array.
4. If no such element is found, it means the target does not have an upper bound in the array, hence return the last index that is length of the array (considering 0 based indexing).

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    // Function to find the upper bound
    int upperBound(vector<int> &nums, int x)
    {
        int n = nums.size();
        // Iterate over each element
        for (int i = 0; i < n; i++)
        {
            /* Return the index if the  
               element is greater than x */
            if (nums[i] > x)
            {
                return i;
            }
        }
        /* If no element is greater 
           than x, return n */
        return n;
    }
};

int main()
{
    vector<int> nums = {3, 5, 8, 9, 15, 19};
    int x = 9;

    // Create an object of the Solution class
    Solution solution;

    // Find the upper bound index for x
    int ind = solution.upperBound(nums, x);

    cout << "The upper bound is the index: " << ind << "\n";

    return 0;
}

Complexity Analysis:

• Time Complexity:O(N), where N is the size of the given array. In the worst case, we have to traverse the entire array, which is the time complexity of the linear search algorithm.
• Space Complexity:O(1), as we are using no extra space to solve this problem.

2️⃣ Binary Search

Intuition:

Here, the idea is to use the fact that the given array is sorted. The linear search algorithm checks each element of the array to arrive at a conclusion. This can be optimized by using binary search, where the search space is halved based on the condition.

In binary search, the upper bound is determined by finding the smallest index for which the element is greater than the target. At each step, check if the element at the middle index (mid) is greater than the target. If it is, store this index as a potential answer and continue searching in the left half of the array, as the smallest possible index for the upper bound must be found.

Approach:

1. Start with initializing 2 end points which mark the search range of the problem. Lets call them low and high where low pointer starts at the first index, and the high pointer points to the last index.
2. Along with this there shall be a need for ans variable initialized to the size of the array. This variable will store the index of the upper bound, or remain as the size of the array if no upper bound is found.
3. Calculate the middle index using simple formula of mid = low + (high - low) / 2.
   1. Compare if the middle index element is greater than the target. In that case update ans with mid (as that can be a potential answer) and search the left half for a smaller index that meets the condition.
   2. If middle index element is less than or equal to the target, move to the right half to continue the search. This reduces the search space by half each time.
4. Repeat this process until the low pointer crosses the high pointer. At the end ans variable will then hold the index of the upper bound.

Dry Run:

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    // Function to find the upper bound
    int upperBound(vector<int>& nums, int x)
    {
        int low = 0, high = nums.size() - 1;
        int ans = nums.size();

        // Binary search to find the upper bound
        while (low <= high) {

            // Calculate mid index
            int mid = (low + high) / 2;

            /*  Update ans if current 
                element is greater than x   */
            if (nums[mid] > x) {
                ans = mid;
                high = mid - 1;
            } 
            // Otherwise, move to the right half
            else {
                low = mid + 1;
            }
        }
        return ans;
    }
};

int main()
{
    vector<int> nums = {1, 2, 2, 3};
    int x = 2;

    // Create an instance of the Solution class
    Solution sol;

    // Function call to find the upper bound
    int ind = sol.upperBound(nums, x);

    cout << "The upper bound is the index: " << ind << "\n";
    return 0;
}

OR

class Solution {
public:
    // Function to find the upper bound index of 'x' in a sorted array 'nums'
    int upperBound(vector<int> &nums, int x) {
        int left = 0;                   // Initialize left pointer to the start of the array
        int right = nums.size() - 1;    // Initialize right pointer to the end of the array
        int ans = nums.size();          // Default answer is set to the size of the array

        while(left <= right) {
            int mid = left + (right - left) / 2; // Calculate mid-point to avoid overflow

            if(nums[mid] == x) {         // If mid element equals 'x'
                left = mid + 1;          // Move to the right half to find the last occurrence of 'x'
            } else if(nums[mid] > x) {   // If mid element is greater than 'x'
                ans = mid;               // Update answer to mid (potential upper bound)
                right = mid - 1;         // Move to the left half
            } else {                     // If mid element is less than 'x'
                left = mid + 1;          // Move to the right half
            }
        }
        return ans;                      // Return the index of the upper bound
    }
};

Complexity Analysis:

• Time Complexity:O(logN), where N is the size of the given array. We are using the Binary Search algorithm, which divides the search space in half each time, resulting in a logarithmic time complexity.
• Space Complexity:O(1), as we are not using any extra space to solve this problem.