lower_bound, upper_bound

lower_bound, upper_bound

lower_bound

찾는 숫자 이상이 처음나오는 index

int lowerBound(vector<int> &nums, int target){
    int size = nums.size();
    int left = 0, right = size;

    while(left < right){
        int mid = left + (right - left) / 2;

        if(target <= nums[mid]){
            // pick left
            right = mid;
        }else if(nums[mid] < target){
            // pick right
            left = mid+1;
        }
    }

    return right;
}

upper_bound

찾는 숫자 초과가 처음 나오는 index

int upperBound(vector<int> &nums, int target){
    int size = nums.size();
    int left = 0, right = size;

    while(left < right){
        int mid = left + (right - left) / 2;

        if(target < nums[mid]){
            // pick left
            right = mid;
        }else if (nums[mid] <= target){
            // pick right
            left = mid + 1;
        }
    }

    return right;
}