Problem Statement

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

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

The lower bound of a target value in a sorted array is defined as the position of the first element that is not smaller than the target. In other words, it finds the first position where the target could be inserted without violating the sorting order.

Examples

Example 1:

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

Explanation: Index 1 is the smallest index such that
arr[1] >= x
2 >= 2

Example 2:

Input: nums = [1, 2, 4, 4, 6, 7], x = 5
Output: 4

Explanation: The lower bound of 5 is 4 (the first number greater than 5,
which is 6).

Example 3:

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

Explanation: The index 0 (3) is equal to the x (3).

Constraints:

• 1 ≤ nums.length ≤ 10^5
• -10^5 <nums[i], x < 10^5
• nums is sorted in ascending order.

Different Approaches

1️⃣ Linear Search (Brute Force)

Intuition:

The brute force approach is to traverse the array linearly to find the lower bound of the given integer 𝑥.

The lower bound is defined as the first element in the array that is greater than or equal to 𝑥. By iterating through the array and comparing each value with 𝑥, we can efficiently identify this position using linear search.

Approach:

1. Iterate through the array and compare each element with the target value, x. Continue this comparison until an element is found that is greater than or equal to the target.
2. The first index, where the element at that index is greater than or equal to target, that will be the lower bound.
3. After the complete iteration of the array, if no such index is found, return the length of the array.

Code:

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

class Solution {
public:
    // Function to find the lower bound
    int lowerBound(vector<int>& nums, int x) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            /* Check the condition for 
               the current element */
            if (nums[i] >= x) {
                // If lower bound is found 
                return i;
            }
        }
        /* If lower bound of 
           target is not found */
        return n;
    }
};

int main() {
    vector<int> arr = {1, 2, 2, 3};
    int x = 2;
    
    // Create an instance of the Solution class
    Solution sol;
    
    // Function call to find the lower bound
    int ind = sol.lowerBound(arr, x);
    
    cout << "The lower 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. This is the time complexity of the linear search algorithm.
• Space Complexity:O(1), no extra space is used to solve this problem.

2️⃣ Binary Search (Optimal)

Intuition:

Since the array is sorted there is a possibility to implement Binary Search algorithm. The goal is to find the smallest index where the element is greater than or equal to the target value, hence by dividing the search space in half and adjusting the pointers based on the comparison results, it is easily possible to get the position of the lower bound.

Lets understand the search space for the problem:

The answer can never lie beyond the array element, if at any case the lower bound is not present and no such element is found in the array, simply return -1. Hence if possible answer are the array elements the search space will be same too. Therefore the low pointer in binary search will point to first index 0, and high that is second pointer will point to last array index that is n-1, where n is length of array.

Approach:

1. Start with two pointers: left at the start and right at the end of the array. Initialize ans to the size of the array.
2. Calculate the middle index, mid, using mid = left (right - high) / 2. If arr[mid] is greater than or equal to x, update ans with mid as this could be the the required result and trim down the search space by eliminating the right half, as the smallest possible index is needed for lower bound, so start searching in the left half of the array. Otherwise, search the right half.
3. Repeat until the right pointer crosses the left pointer. The ans will hold the index of the lower bound if found, or the size of the array if no such index exists.

Dry Run:

Code:

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

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

        while (low <= high) {
            int mid = low + (high - low) / 2; 

            /* Check if mid element 
               is a potential answer */
            if (nums[mid] >= x) {
                ans = mid; 

                // Search left half
                high = mid - 1; 
            } 
            else {
                // Search right half
                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 lower bound
    int ind = sol.lowerBound(nums, x);

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

OR

class Solution {
public:
    // Function to find the lower bound index of 'x' in a sorted array 'nums'
    int lowerBound(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'
                ans = mid;               // Update answer to current mid index
                right = mid - 1;         // Move to the left half to find the first occurrence
            } else if(nums[mid] > x) {   // If mid element is greater than 'x'
                ans = mid;               // Update answer to mid (potential lower 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 lower bound
    }
};

Complexity Analysis:

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