이분탐색 알고리즘

이분탐색 알고리즘은 쉬우면서도 어렵고, 어려우면서도 쉬운 알고리즘인 듯하다.

이번 포스팅에서는 이분탐색 알고리즘과 그와 연계되어서 자주 나오는 lower/upper bound 알고리즘에 대해서 정리해보자.

 

---

1. 개념

이분탐색은 정렬된 리스트에서 원하는 값을 위치에 상관 없이 하나를 찾는 알고리즘이다.

 

lower/upper bound는 이분탐색의 목적과 살짝 다르다.

이분탐색은 특정 K 값을 찾으면 바로 종료를 하지만, lower/upper bound는 경계를 찾는 알고리즘으로 특정 K 값을 찾았다고 종료해서는 안 된다.

 

간단히 정리하면 다음과 같다.

• lower_bound: 특정 K 이상 값이 처음으로 등장하는 위치
• upper_bound: 특정 K 초과 값이 처음으로 등장하는 위치

 

특히 이분탐색과 관련된 코드는 (<, <=)와 (left = mid, left = mid+1) 과 같이 수식 하나의 차이로 그 결과가 다르게 나와 틀리는 경우도 많다. 이 부분은 코드와 함께 살펴보자.

 

---

2. 코드 이해

1-1. 이분탐색 

1) `while left <= right`

• `while left < right`로 정의하면 `left = right`인 마지막 원소를 탐색하는 시점에 종료하게 된다. (return -1)
• 따라서 마지막 원소까지 정확히 탐색을 하고, 정답의 유무를 판단하기 위해서 반드시 `<=`를 사용해야 한다.

 

2) `left = mid + 1`, `right = mid - 1`

• `if arr[mid] == k` 문에서 mid에 위치한 값을 확인했기 때문에, mid ± 1 로 범위를 제한해준다.

def binary_search(arr, k):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == k:
            return mid
        elif arr[mid] < k:
            left = mid + 1
        else:
            right = mid - 1

    return -1

 

 

1-2. lower_bound 기반 이분탐색

아래의 lower bound를 먼저 읽으면 이해하기 훨씬 수월하다.

 

1) `if left < len(arr) and arr[left] == k:`

• lower bound에서는 배열 원소 중에 K 이상이 없을 시, len(arr) 현재 배열의 인덱스를 넘어선 값을 반환해준다.
  • len(arr) = K를 넣어도 정렬이 유지되는 위치
• 하지만 이분탐색의 목적은 정확히 K 값이 위치한 인덱스이다. 따라서 lower bound에서 len(arr)을 반환하더라도, 현재 배열에는 K 값이 존재하지 않으므로, `left < len(arr)`로 현재 배열의 크기를 초과하였는지 검증하여 -1 을 반환해야 한다.

def binary_search(arr, k):
    left = 0
    right = len(arr)

    while left < right:
        mid = (left + right) // 2

        if arr[mid] < k:
            left = mid + 1
        else:
            right = mid

    if left < len(arr) and arr[left] == k:
        return left
        
    return -1

 

 

2. lower bound

→ 특정 K 이상이 처음으로 등장하는 위치

 

1) `right = len(arr)`

• 배열 원소 중에 K 이상이 없을 시, 배열의 제일 마지막을 반환해주기 위해서다.
• 정확히는 arr 배열의 마지막 + 1 위치에 k를 넣어도 정렬이 유지되게끔 하는 위치이다.
  • K 이상이 처음 나오는 위치 = K를 넣어도 정렬이 유지되는 위치

 

2) `while left < right`

• 이분탐색과 같이 K를 찾으면 탈출하는 구조가 아닌, K 이상이 처음으로 등장하는 경계값을 찾는 알고리즘이다.
• 따라서 left = right 가 되었을 때 경계값을 찾고 반복문을 탈출해야 되지만, `while left <= right` 로 정의하면 무한 루프에 빠지게 된다.

 

3) `else: right = mid`

• `arr[mid] < k`에서는 arr[mid] 값이 K 미만의 값이 되므로, K 이상이 처음으로 등장하는 위치를 찾는 lower bound에서는 정답이 될 수가 없다. 따라서 `left = mid + 1`로 정의하여 후보군을 좁히면 된다.
• 그 반대인 `arr[mid] >= k`에서는 K 이상의 값이므로 mid 인덱스가 정답 후보가 될 수 있으므로, `right = mid`로 정의해야 한다. 

def lower_bound(arr, k):
    left = 0
    right = len(arr)

    while left < right:
        mid = (left + right) // 2

        if arr[mid] < k:
            left = mid + 1
        else:
            right = mid

    return left

 

 

3. upper_bound

→ 특정 K 초과가 처음으로 등장하는 위치

 

lower bound에서 잘 이해가 되었다면, upper bound도 자연스럽게 이해할 수 있다.

 

1) `if arr[mid] <= k`

• `arr[mid] < k`에서는 arr[mid] 값이 K 이하의 값이 되므로, K 초과가 처음으로 등장하는 위치를 찾는 upper bound에서는 정답이 될 수가 없다. 따라서 `left = mid + 1`로 정의하여 후보군을 좁히면 된다.
• 그 반대인 `arr[mid] > k`에서는 K 초과의 값이므로 mid 인덱스가 정답 후보가 될 수 있으므로, `right = mid`로 정의해야 한다.

def upper_bound(arr, k):
    left = 0
    right = len(arr)

    while left < right:
        mid = (left + right) // 2

        if arr[mid] <= k:
            left = mid + 1
        else:
            right = mid

    return left

 

 

---

3. 문제

지금까지 풀었던 이분탐색 유형에 대한 문제 풀이 리스트이다.

 

 

* BOJ - 2417. 정수 제곱근 (실버 4)

• https://wch-0625.tistory.com/44

 

* BOJ - 19637. IF문 좀 대신 써줘 (실버 3)

• https://wch-0625.tistory.com/45

 

* BOJ - 11663. 선분 위의 점 (실버 3)

• https://wch-0625.tistory.com/48

 

* BOJ - 13397. 구간 나누기 2 (골드 4)

• https://wch-0625.tistory.com/47

* BOJ - 1939. 중량제한 (골드 3)

• https://wch-0625.tistory.com/58

 

* BOJ - 1300. K번째 수 (골드 1)

• https://wch-0625.tistory.com/56