Lower Bound

The lower bound algorithm finds the first and 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 there is no such index we usually return length of the array.

 int lowerBound(vector<int> &nums, int x)
    {
        int l = 0, r = nums.size();
        int ans = -1;
        while (l <= r)
        {
            int m = (l + r) / 2;
            if (nums[m] >= x)
            {
                ans = m;
                r = m - 1;
            }
            else
                l = m + 1;
        }
        return ans == -1 ? nums.size() : ans;
    }

Upper Bound

The upper bound algorithm finds the first and smallest index in a sorted array where the value at that index is greater than a given key i.e. x.

int upperBound(vector<int> &nums, int x)
    {
        int l = 0, r = nums.size()-1;
        int ans = r;
        while (l <= r)
        {
            int m = (l + r) / 2;
            if (nums[m] > x)
            {
                ans = m;
                r = m - 1;
            }
            else
                l = m + 1;
        }
        return ans;
    }