binarySearch 이진탐색의 lowerBound, upperBound (중복 원소 중 첫번째 인덱스와 마지막 인덱스 구하기)

lowerBound

[1, 1, 2, 2, 2, 2, 3] 의 배열에서 2가 나오는 첫번째 인덱스를 구하고 싶은 경우

 

...
    /**
     * 처음으로 나오는 target 보다 작은 수
     */
    private static int lowerBound() {
        int start = 0;
        int end = arr.length; // start 가 마지막 인덱스 직전까지 체크되어야한다.

        while (start < end) {
            int mid = (start + end) / 2;

            /* target 이 중간값보다 작거나 같다면, 끝을 중간값으로 */
            if (X <= arr[mid]) {
                end = mid;
            } else { /* target 이 중간값보다 크다면 시작을 중간값 다음으로 */
                start = mid + 1;
            }
        }

        System.out.println("lowerBound low : " + start);
        return start;
    }
...

 

 

 

upperBound

[1, 1, 2, 2, 2, 2, 3] 의 배열에서 2가 아닌 원소가 나오는 첫번째 인덱스를 구하고 싶은 경우

 

...
    /**
     * 처음으로 나오는 target 보다 큰 수
     */
    private static int upperBound() {
        int start = 0;
        int end = arr.length;
        
        while (start < end) {
            int mid = (start + end) / 2;

            if (X >= arr[mid]) { /* target 이 중간값보다 크거나 같다면, 시작을 중간값 다음으로 */
                start = mid + 1;
            } else { /* target 이 중간값보다 작다면 끝을 중간값으로 */
                end = mid;
            }
        }

        System.out.println("upperBound low : " + start);
        return start - 1;
    }
...

 

그러므로, 원소 2가 나오는 마지막 인덱스는 start -1 이 된다.