Lower Bound and Upper Bound
Kanav Arora
17001
Binary SearchCcodingCareer

Lower bound is the first occurrence of target element. If element not found index of first element greater than target is returned.

Upper bound is the first occurence of element greater than target element.

More codes: https://github.com/Kanav-Arora/DSA-Cpp

C++ implementation using binary search:

Lower Bound

int lower_bound(vector<int> nums, int target)
{
    int start = 0;
    int end = nums.size()-1;
    int mid = 0;
    while(start<end)
    {
        mid = start  + (end-start)/2;
        if(nums[mid]<target)    start = mid+1;
        else   end = mid;
    }
    return start;
}

Input:
[1,2,3,4,6,6,8,11]
6

Output:
4

Upper Bound

int upper_bound(vector<int> nums, int target)
{
    int start = 0;
    int end = nums.size()-1;
    int mid = 0;
    while(start<end)
    {
        mid = start  + (end-start)/2;
        if(nums[mid]<=target)    start = mid+1;
        else   end = mid;
    }
    return start;
}

Input:
[1,2,3,4,6,6,8,11]
6

Output:
6

Comments (5)