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

1. 1. 서론

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

 

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

 

 

 

2. 2. Lower bound

Lower bound 알고리즘

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

 

2.1. 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. 2.2  low bound 구현

      

      

      

    
    

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

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

         else
            higt = mid;
    }       
    
    return high;

 

 

 

 

3. 3. Upper bound

Upper bound 알고리즘

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

 

 

3.1. 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. 3.2 Upper bound 구현

      

      

      

    
    

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

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

         else
            higt = mid;
    }       
    
    return high;

 

 

 

 

 

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

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

 

 

 

 

 

5. 5. 결론

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

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

 

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

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

 

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