파이썬, Lower Bound 및 Upper Bound 구현

구현 전, 알아두어야 할 것 

Lower Bound 및 Upper Bound는 모두 경계값을 찾는 함수다. 이 함수는 반드시 정렬이 된 값들에서만 사용할 수 있다.

---

Lower Bound 파이썬 코드 구현 : O(logn)

Lower Bound는 찾고자 하는 값이 가장 처음으로 나오는 위치를 찾는 함수다. 예를 들어, 4를 찾는다면 4가 가장 처음으로 나오는 위치를 찾는 함수다. 아래 표를 예시로 들 경우, Index는 6이 정답이 된다. 

Index	0	1	2	3	4	5	6	7	8
Value	1	1	1	2	2	3	4	4	4

Lower Bound 함수를 구현할 때, 나는 다음과 같이 구현했다. 

1. 이진 검색을 기준으로 값을 찾는다. (logn의 시간복잡도 구현)
2. 이진 검색 시, 다음과 같은 로직으로 접근한다. 
 2-1. 현재 Mid값이 찾고자 하는 값보다 작은 경우, Left = Mid + 1 
 2-2. 현재 Mid값이 찾고자 하는 값보다 큰 경우, Right = Mid - 1
 2-3. 현재 Mid값이 찾고자 하는 값과 같을 경우, Right = Mid
   (단, 2-3에서 무한 루프 방지를 위해 right와 mid가 같을 경우 Break를 걸어준다) 
3. While문이 완료되면, 현재 Left, Right 값을 기준으로 Mid를 구한다. 그 후 Mid에 있는 값을 기준으로 판별한다.  
  3-1. Mid에 있는 값이 찾고자 하는 값이면, Mid를 Return 한다. 
  3-2. Mid에 있는 값이 찾고자 하는 값이 아니면, -1를 Return한다. 

현재 Mid값이 찾고자 하는 값보다 작은 경우에는 이 부분부터 왼쪽 부분은 더 이상 살펴볼 필요가 없어진다. 또한 이 값보다 큰 경우 역시 살펴볼 필요가 없기 때문에 오른쪽 부분은 더 이상 살펴볼 필요가 없어진다. 따라서 각각에 대해 Left = Mid + 1 , Right = Mid -1 을 적용하게 되었다. 

우리가 계속 꾸준히 살펴봐야하는 부분은 Mid가 찾고자 하는 값일 때이다. 이건 처음으로 그 수가 나오는 것을 찾는 것이기 때문에, 지금 살펴본 Mid가 처음일 수도 있다. 따라서 이 부분을 빼고 탐색을 하는 것은 안되기 때문에 이 섹터의 값은 항상 저장해두어야 한다. 

단, 이 값이 처음으로 나오는 인덱스를 살피는 것이기 때문에 논리상 Right = Mid를 적용하는 것이 맞다. Right = Mid를 적용해두면, 여러 개의 똑같은 값이 나올 때 Right의 값이 점차 왼쪽으로 접근한다. 즉, 이 값이 나오는 가장 처음의 위치를 알 수 있다. 이걸 살짝 응용하면 Left = Mid를 하게 될 경우, Left의 값이 점차 오른쪽으로 접근 하기 때문에 이 값이 나오는 가장 마지막 위치를 알 수 있다. 

 

파이썬으로 짠 코드는 다음과 같다.

def lower_bound(left, right, k) :
    while left <= right :
        mid = (left + right) // 2
        if my_list[mid] < k :
            left = mid + 1
        elif my_list[mid] > k  :
            right = mid - 1
        elif my_list[mid] == k :
            if right == mid :
                break
            right = mid
    if my_list[mid] == k :
        return mid
    else :
        return -1

위의 과정을 하나하나 도식화해서 그려보면 아래와 같아 진다. 

마지막에 L,R,M이 두번 나오게 되는데, 내가 짠 코드는 이 때 루프가 중단된다. 왜냐하면 시작했을 때의 Mid와 Right가 같아지는 지점이 되기 때문이다. 

---

Upper Bound 파이썬 코드 구현 : O(logn)

Upper Bound는 찾고자 하는 값보다 큰 값이 가장 처음으로 나오는 위치를 찾는 함수다. 예를 들어, 2를 찾는다면 2보다 큰 값이 가장 처음으로 나오는 위치를 찾는 함수다. 아래의 표에서는 Value 3이 답을 만족하기 때문에 Index 5가 Return 된다.

Index	0	1	2	3	4	5	6	7	8
Value	1	1	1	2	2	3	4	4	4

 

Upper Bound 함수를 구현할 때, 나는 다음과 같이 구현했다. 

1. 이진 검색을 기준으로 값을 찾는다. (logn의 시간복잡도 구현)
2. 이진 검색 시, 다음과 같은 로직으로 접근한다. (While문을 다 돌 때까지 기다린다)
 2-1. 현재 Mid값이 찾고자 하는 값보다 작거나 같은 경우, Left = Mid + 1 
 2-2. 현재 Mid값이 찾고자 하는 값보다 큰 경우, Right = Mid 
3. While문이 완료되면, 현재 Left, Right 값을 기준으로 Mid를 구한다. 그 후 Mid에 있는 값을 기준으로 판별한다. 
  3-1. Mid에 있는 값이 찾고자 하는 값이면, Mid를 Return 한다. 
  3-2. Mid에 있는 값이 찾고자 하는 값이 아니면, -1를 Return한다. 

Mid 값이 찾고자 하는 값보다 작거나 같은 경우는 Left의 값을 Mid + 1 로 주게 되는데, 이 이유는 찾고자 하는 값보다 작거나 같은 경우는 우리가 고려하는 경우가 아니기 때문에 더 이상 보지 않아도 되기 때문이다. 반대로 Mid 값이 찾고 하는 값보다 큰 경우에는 우리가 반드시 고려해야하는 부분이기 때문에 Right = Mid로 하여 앞으로 계속 고려해주는 것이다. 

파이썬으로 짠 코드는 다음과 같다.

def upper_bound(left, right, k) :
    while left < right :
        mid = (left + right) // 2
        if my_list[mid] <= k :
            left = mid + 1
        elif my_list[mid] > k :
            right = mid
    mid = (left + right) // 2
    if my_list[mid] > k :
        print(mid)
    else :
        print(-1)

 

위의 과정을 하나하나 도식화해서 그려보면 아래와 같아진다.