JAVA : Uppered Bounded

    public static int UpperBounded(int left, int right, int r, ArrayList<Pair> list) {
 
        if (left == right) {
            if (left == list.size() - 1) {
                if (list.get(left).r >= r)
                    return -1;
            }
 
            return left;
 
        }
 
        int mid = (left + right) / 2;
 
        if (list.get(mid).r < r) {
            // 왼편에있다.
            return UpperBounded(left, mid, r, list);
        } else {
            return UpperBounded(mid + 1, right, r, list);
        }
    }

정의

증가하거나 감소하는 배열에 대해서 사용할 수 있다.
2진탐색이 어떤값의 인덱스를 첨음 찾는 탐색이라면 Uppered Bounded는 어떤 특정값을 초과하거나 미만이되는 값을 찾는 방법이다.

위에방법은 어떤값 r에대해서 보다 작은값이 왼쪽에서부터 탐색햇을때 가장먼저 나오는지 탐색한다.
이진탐색과 다른점은 mid값을 제외한 좌우지만 BuffedBounded는 mid값을 포함한다.
반환은 left==right가 같아지는 시점이 후보인데 조건이 만족하지않으면
그배열에는 특정 조건을 만족하는 배열이 없다고 판단 하여 ' -1 ' 을 반환한다.