Upper_bound와 Lower_bound란?

 

어떤 리스트에서 이분 탐색을 이용하여 특정 값을 찾을 때, 리스트가 중복된 값을 포함하고 있을 때 중복 값들을 전부 찾거나 또한 그 중복값들을 활용해서 문제를 해결하기 위해서 lower_bound, upper_bound를 사용하면 특정 target number 보다 크거나 같은 첫 번째 원소 인덱스, target number보다 큰 첫번째 원소의 인덱스를 찾을 수 있습니다.

 

이진 탐색을 이용하기 때문에 리스트는 항상 정렬되어 있어야 합니다.

 

hashFunction을 이용하여 중복된 값들의 개수를 탐색하면 O(1)이라 훨씬 더 빠르게 탐색할 수 있을 것 같은데..?라는 생각이 들긴 합니다.

 

하지만 특정 구간의 범위를 지정하기 위해서는 유용하게 사용할 수 있을 것 같습니다.

 

upper_bound

범위 [begin, end) 안의 원소들 중, 특정 Target Number보다 큰 첫 번째 원소의 인덱스를 반환합니다.

만약 해당 원소가 존재하지 않는다면 end 인덱스를 반환합니다.

private static int upperBound(List<Integer> data, int targetNumber) {
    int begin = 0;
    int end = data.size();
    
    while(begin < end) {
    	int mid = (begin + end) / 2;
        
        if(data.get(mid) <= targetNumber) {
        	begin = mid + 1;
        }
        else {
        	end = mid;
        }
    }
    return end;
}

 

 

lower_bound

범위[begin, end) 안의 원소들 중, 특정 Target Number보다 크거나 같은 첫번째 원소의 인덱스를 반환합니다.

만약 해당 원소가 없다면 end 인덱스를 반환합니다.

private static int lowerBound(List<Integer> data, int targetNumber) {
    int begin = 0;
    int end = data.size();
    
    while(begin < end) {
    	int mid = (begin + end) / 2;
        
        if(data.get(mid) >= targetNumber) {
        	end = mid;
        }
        else {
        	begin = mid + 1;
        }
    }
    return end;
}

 

마무리

이분 탐색을 활용하기 때문에 정렬된 리스트에 사용할 수 있습니다.

또한 시간 복잡도는 O(logN)입니다.

 

 

 

출처

https://velog.io/@junhok82/lowerbound-upperbound

Java로 upper_bound와 lower_bound 구현하기