Java로 upper_bound와 lower_bound 구현하기

김준호·2020년 6월 9일
3

알고리즘

목록 보기
3/7
post-thumbnail

어떤 리스트에서 이분탐색을 이용해서 특정 값을 찾을때, 리스트가 중복된 값을 포함하고 있을 수 있다. 그 중복값을 전부 찾거나 또한 그 중복값들을 활용해서 문제를 해결하는 문제를 위해서 upper_bound나 lower_bound가 존재한다.

역시나 마찬가지로 이 함수는 c++의 Algorithm.h 헤더에서 제공해준다. 이를 참고해서 java에서 구현해보도록 하자.


lower_bound

범위 [begin, end) 안의 원소들 중, 특정 target보다 크거나 같은 첫번째 원소의 인덱스를 리턴한다. 만약 그런 원소가 없다면 end 인덱스를 리턴한다.

이때 리스트는 모두 정렬된 상태여야 한다. 즉, lower_bound가 성립하기 위해서는 각각의 요소들중 element < target를 만족하는 요소들은 만족하지 않는 요소들보다 앞에 있어야한다.

c++의 lower_bound를 확인해보면 아래와같이 구성되어있다.

template <class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value);

인자로 (리스트의 시작, 리스트의 끝, 찾고자하는 값)을 받고있다. 그리고 앞에서 언급했다시피 리턴값은 찾고자하는 값의 첫번째 인덱스를 리턴하기 때문에, 고려해서 java로 작성해보자.

구현

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

upper_bound

범위 [begin, end) 안의 원소들 중, 특정 target보다 큰 첫번째 원소의 인덱스를 리턴한다. 만약 그런 원소가 없다면 end 인덱스를 리턴한다.

이때 리스트는 모두 정렬된 상태여야 한다. 즉, upper_bound가 성립하기 위해서는 각각의 요소들중 element <= target를 만족하는 요소들은 만족하지 않는 요소들보다 앞에 있어야한다. lower_bound와 비교해보면 등호가 들어가는데, target보다 큰 인덱스를 구하기 위해서이다.

c++의 upper_bound를 확인해보면 아래와같이 구성되어있다.

template <class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value);

인자로 (리스트의 시작, 리스트의 끝, 찾고자하는 값)을 받고있다. 그리고 앞에서 언급했다시피 리턴값은 찾고자하는 값보다 큰 값의 첫번째 인덱스를 리턴하기 때문에, 고려해서 java로 작성해보자.

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

정리

기본적으로 이분탐색의 원리를 따르기때문에 시간복잡도는 O(logn)이고, 정확히는 O(long(리스트의 길이))다. 두 함수를 구축할때 팁은 어떤 값을 찾고자하는지 생각하면 된다.

그리고 return값을 upperbound에서 target보다 큰 인덱스값을 뽑아내는 이유는 아마,
upperBound() - lowerBound()를 통해서 중복값의 개수를 구하기 위해서이지 않을까 생각한다.

profile
https://junhok82.github.io/

0개의 댓글