lower_bound / upper_bound

class Solution {
public:
    int binarySearchLowerBound(int left, int right, vector<int> arr, int target){
        // upper bound
        while(left < right){
            int mid = left + (right - left) / 2;
            
            if(arr[mid] <= target){
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    int binarySearchUpperBound(int left, int right, vector<int> arr, int target){
        // lower bound
        while(left < right){
            int mid = left + (right - left) / 2;
            if(arr[mid] < target){
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    vector<int> avoidFlood(vector<int>& rains) {
        set<int> ans = {1,2,3,4,5,6,7,8};
        
        auto it = ans.upper_bound(4); // 5
        int v = *it;
        it = ans.lower_bound(4); // 4
        v = *it;
        
        int a = binarySearchLowerBound(0, 7, {1,2,3,4,5,6,7,8}, 4); // 4
        int b = binarySearchUpperBound(0, 7, {1,2,3,4,5,6,7,8}, 4); // 5
        return {};
    }
};

 lower_bound는 target 값이 주어지면 sorted list에서 target보다 같거나 큰 수의 집합에서 가장 작은 값의 iteration을 리턴한다.

 upper_bound는 target 값이 주어지면 sorted list에서 target보다 큰 수의 집합에서 가장 작은 값의 iteration을 리턴한다.

 

 ans.upper_bound(ans.begin(), ans.end(), target); 처럼 sorted list에서 범위를 특정할 수도 있다.