[알고리즘] Lower bound와 Upper bound 개념과 구현 - Java

1. 서론

이분 탐색 알고리즘 관련 문제를 풀다가 잘 이해가 안되는 부분이 2가지 있었는데 바로 원하는 값과 탐색 값이 같을 때 어디서 처리를 해야할지, 두 번째로 low와 high값 중 어떤 것을 결과로 선택 해야할지이다. 

 

여러 블로그들을 방문하여 내가 고민했던 문제를 어떻게 생각했는지 알아봤는데 설명이 잘 되어있는 블로그에서는 대부분 Lower bound와 Upeer bound 중 하나를 선택해서 구현했다. 그래서 이 두 개념에 대해 알아보고자 한다!

 

 

 

2. Lower bound

Lower bound 알고리즘

찾고자 하는 값(크거나 같은)의 시작위치를 알아낸다.
시간 복잡도 : O(logn)

 

2.1  동작 방식

1. 배열의 중간 값을 가져온다.

2. 중간 값과 검색값을 비교한다.

• 중간 값이 검색 값보다 작으면 low값을 mid+1로 한다.
• 중간 값이 검색 값보다 크거나 같으면 high값을 mid로 한다.

3. low < high 일 때까지 1번과 2번을 반복한다.

4. 반복이 끝나면 high값이 lower bound가 된다.

 

이진 탐색과 다른 점은 high = mid-1로 mid를 포함하지 않지만 Lower나 Upper는 mid를 포함하여 변경한다. 

따라서 최종 연산 후에는 언제나 결과값이 high에 위치하게 된다.

 

참고 : 설명이 아주 잘 되었있는 블로그 - https://yoongrammer.tistory.com/105

Lower bound & Upper bound 개념 및 구현

 

2.2  low bound 구현

    while(low < high){
        mid = (low+high)/2;

        if(arr[mid] < k)
            low = mid+1;

         else
            higt = mid;
    }       
    
    return high;

 

 

 

 

3. Upper bound

Upper bound 알고리즘

특정 값보다 처음으로 큰 값(초과)의 위치를 찾는다.
시간 복잡도 : O(logn)

 

 

3.1 동작 방식

1. 배열의 중간 값을 가져온다.

2. 중간 값과 검색값을 비교한다.

• 중간 값이 검색 값보다 작거나 같으면 low값을 mid+1로 한다.
• 중간 값이 검색 값보다 크면 high값을 mid로 한다.

3. low < high 일 때까지 1번과 2번을 반복한다.

4. 반복이 끝나면 high값이 Upper bound가 된다.

 

Lower bound와 대체 무슨 차이가있지 싶을 것이다. 바로 차이는 중간 값이 검색값과 같으면 `Lower`는 high를 변경하지만,

`Upper`는 low를 변경한다. 왜냐하면 Upper는 초과 값을 찾아야 하기 때문에 결과 값인 high를 바꾸면 안되고 low값을 증겨시켜야 한다.

 

 

3.2 Upper bound 구현

    while(low < high){
        mid = (low+high)/2;

        if(arr[mid] <= k)
            low = mid+1;

         else
            higt = mid;
    }       
    
    return high;

 

 

 

 

 

4. 이진 탐색과 Lower, Upper bound의 차이점

	이진 탐색	Lower, Upper bound
탐색을 그만하는 시점	low > high	low >= high
high의 변경	high = mid -1	high = mid

 

 

 

 

 

5. 결론

1. 원하는 값과 탐색 값이 같을 때 어디서 처리?

->  원하는 값이 초과하는 값이면 low에서 처리하고, 딱 맞는 값을 원하면 high에서 처리한다.

 

2. low와 high중 어떤 값을 결과값으로?

-> 리턴은 무조건 high이다. 경우에 따라 high에 -1를 하기도 한다.

 

사실 모든 문제에 딱 맞는 솔루션은 없다. 본인이 편할대로 틀을 잡아놓고 문제에 따라 미세하게 조정하며 풀어야한다. 예를 들어 while문에서 빠져나가는 기준이나, 어떤 값을 리턴할지 등은 상황에 따라 바뀐다.