[알고리즘] Upper Bound, Lower Bound

서론

Upper Bound, Lower Bound는 이진탐색을 활용한 알고리즘이다.

 

[알고리즘] 이진탐색(이분탐색) - Binary Search

 

백준에서 이진탐색을 활용한 문제를 풀다가, 깔끔하게 풀리지 않아서 풀고 난 뒤 다른 분들의 코드나 설명을 참조했더니, 내가 사용했던 조건들이 Upper Bound라는 것을 알게되었고, 정리하고자 포스팅을 진행한다.

[백준 1654번 / JAVA] 랜선 자르기

 

 

정의

이진 탐색의 과정에서

Upper Bound는 탐색하고자 하는 숫자보다 큰 첫 번째 위치를 탐색하며,

Lower Bound는 크거나 같은 첫 번째 위치를 탐색한다.

쉽게 말해 Upper Bound는 초과, Lower Bound는 이상. 이라는 소리다

 

 

 

 

Upper Bound

Upper Bound : n을 초과하는 첫 번째 idx 탐색

 

아래는 Upper Bound를 구현한 자바 코드이다.

public static void main(String[] args) throws IOException{    	
    int[] arr = new int[] {1,3,3,5,6,7};
    int n = 3;
    int left = 0;
    int right = arr.length-1;
    int mid;
    
    while(left<right){
        mid = (left + right) / 2;
        
        if(arr[mid] > n) right = mid;
        else left = mid + 1;
    }
    
    System.out.println(right);

}

우선, 이진 탐색처럼 해당 값에 딱 맞아 떨어지는 인덱스를 구하는 것이 아니기 때문에 while문 안의 조건을 left < right로 두고, arr[mid]==n의 조건도 없다.

 

또한 n보다 큰 첫 번째 위치를 찾는 것이기 때문에, n보다 크다면, right를 mid로 초기화시켜, mid의 범위를 포함하도록 해야한다.

 

 

 

Lower Bound

Lower Bound : n이상의 값을 가지는 첫 번째 idx 탐색

public static void main(String[] args) throws IOException{    	
    int[] arr = new int[] {1,3,3,5,6,7};
    int n = 3;
    int left = 0;
    int right = arr.length-1;
    int mid;
    while(left<right){
        mid = (left + right) / 2;
        if(arr[mid] >= n) right = mid;
        else left = mid + 1;
    }
    System.out.println(right);

}

위의 Upper Bound 알고리즘을 이해했다면, Lower Bound는 설명할 것도 없다.

"이상" 의 경우를 포함해야 하기 때문에 위의 Upper Bound에서 등호 한개만 추가해 주면 된다.

if(arr[mid] >= n) right = mid;

 

 

 

마치며

이분탐색과 Upper Bound, Lower Bound 알고리즘을 적절히 잘 활용하면, 반대로 미만, 이하의 값도 손쉽게 구할 수 있을 것이고, 결과적으로 이분탐색을 활용해야 하는 문제 해결에 있어 어렵지 않게 대처할 수 있을 것 같다.