BinarySearch (이분 탐색)

Binary Search

Binary Search(이분 탐색)는 정렬된 배열이나 수의 범위에서 특정 값을 효율적으로 찾기 위한 알고리즘입니다. 중간 값을 기준으로 원하는 값이 왼쪽 구간에 있는지, 오른쪽 구간에 있는지를 판단하여 탐색 범위를 절반씩 줄여나가는 방식으로 동작합니다.

• 탐색 범위를 매번 절반으로 줄이므로 시간 복잡도는 O(log N)으로 매우 효율적입니다.

이분 탐색은 일반 이분탐색, Lower Bound, Upper Bound 로 나눌 수 있습니다.

Mechanism

가장 기본적인 이분 탐색은 정렬된 배열에서 특정 값을 정확히 찾는 경우에 사용됩니다. 그 동작 과정은 다음과 같습니다.

1. 시작 인덱스 left와 끝 인덱스 right를 설정합니다. (left = 0, right = len(arr) - 1)
2. 중간 지점 mid = (left + right) // 2를 계산합니다.
3. arr[mid] 값과 찾고자 하는 값 target을 비교하여 탐색 범위를 절반으로 줄입니다.
   • target == arr[mid]인 경우: 값을 찾았으므로 mid를 반환합니다.
   • target < arr[mid]인 경우: 탐색 대상이 왼쪽 구간에 있으므로 right = mid - 1로 이동합니다.
   • target > arr[mid]인 경우: 탐색 대상이 오른쪽 구간에 있으므로 left = mid + 1로 이동합니다.
4. 2,3 과정을 left <= right 조건을 만족하는 동안 반복합니다.

정렬된 데이터를 기반으로 BinarySearch(5)를 구해보겠습니다. 가장 먼저 left, right 를 각각 0, 7로 설정합니다.

1. 중간 지점을 계산합니다. (left + right) // 2 = 3
   • 탐색 대상 5가 중간 지점 값 6보다 왼쪽에 있으므로 right = mid - 1하여 탐색 범위를 탐색 범위를 왼쪽 절반으로 줄입니다.
2. 다시 중간 지점을 계산합니다.
   • 탐색 대상 5가 중간 지점 값 4보다 오른쪽에 있으므로 left = mid + 1하여 탐색 범위를 오른쪽 절반으로 줄입니다.
3. 다시 중간 지점을 계산합니다.
   • 탐색 대상 5가 중간 지점 값과 같으므로 mid 를 반환하고 탐색을 종료합니다.

이번에는 BinarySearch(14)를 구해보겠습니다. 가장 먼저 left, right 를 각각 0, 7로 설정합니다.

1. 중간 지점을 계산합니다. (left + right) // 2 = 3
   • 탐색 대상 14가 중간 지점 값 6보다 오른쪽에 있으므로 left = mid + 1하여 탐색 범위를 오른쪽 절반으로 줄입니다.
2. 다시 중간 지점을 계산합니다.
   • 탐색 대상 14가 중간 지점 값 12보다 오른쪽에 있으므로 left = mid + 1하여 탐색 범위를 오른쪽 절반으로 줄입니다.
3. 다시 중간 지점을 계산합니다.
   • 탐색 대상 14가 중간 지점 값과 같으므로 mid 를 반환하고 탐색을 종료합니다.

이번에는 BinarySearch(11)를 구해보겠습니다. 가장 먼저 left, right 를 각각 0, 7로 설정합니다.

1. 중간 지점을 계산합니다. (left + right) // 2 = 3
   • 탐색 대상 11이 중간 지점 값 6보다 오른쪽에 있으므로 left = mid + 1하여 탐색 범위를 오른쪽 절반으로 줄입니다.
2. 다시 중간 지점을 계산합니다.
   • 탐색 대상 11이 중간 지점 값 12보다 왼쪽에 있으므로 right = mid - 1하여 탐색 범위를 왼쪽 절반으로 줄입니다.
3. 다시 중간 지점을 계산합니다.
   • 탐색 대상 11이 중간 지점 값 10보다 오른쪽으로 있으므로 left = mid + 1하여 탐색 범위를 오른쪽 절반으로 줄입니다.
   • left < right 가 되었으므로 탐색이 종료됩니다. 하지만, 이전에 mid 값을 리턴한 적이 없으므로, 찾을 수 없었다는 의미로 -1 를 반환합니다.

Lower Bound

Lower Bound Search는 찾고자 하는 값보다 크거나 같은 값 중에서 가장 작은 값의 위치를 반환하는 이분 탐색 방법입니다. 즉, target <= arr[i] 를 만족하는 최소 인덱스를 구할 수 있습니다.

1. 시작 인덱스 left와 끝 인덱스 right를 설정합니다. 이때 right = len(arr)로 설정합니다.
2. 중간 지점 mid = (left + right) // 2를 계산합니다.
3. arr[mid]와 target을 비교해 탐색 범위를 반으로 줄입니다.
   • target <= arr[mid]인 경우: mid는 정답 후보일 수 있으므로 right = mid로 이동합니다.
   • target > arr[mid]인 경우: mid는 정답이 될 수 없으므로 left = mid + 1로 이동합니다.
4. 2,3 과정을 left < right인 동안 반복합니다.
5. 반복 종료 시 left 또는 right가 Lower Bound 결과를 가리킵니다.

정렬된 데이터를 기반으로 LowerBound(11)를 구해보겠습니다. 가장 먼저 left, right 를 각각 0, 8로 설정합니다.

1. 중간 지점을 계산합니다. (left + right) // 2 = 4
   • 중간 값 10은 탐색 대상 11보다 작으므로 정답 후보가 될 수 없습니다. 이는 정답 후보들이 최소한 mid보다 오른쪽 있다는 것을 의미합니다. 따라서 left = mid + 1하여 탐색 범위를 오른쪽 절반으로 줄입니다.
2. 다시 중간 지점을 계산합니다.
   • 중간 값 14는 탐색 대상 11보다 크므로 정답 후보가 될 수 있습니다. 이는 정답 후보들이 mid를 포함한 왼쪽에 있다는 것을 의미합니다. 따라서 rigt = mid하여 탐색 범위를 mid를 포함한 왼쪽 절반으로 줄입니다.
3. 다시 중간 지점을 계산합니다.
   • 중간 값 12는 탐색 대상 11보다 크므로 정답 후보가 될 수 있습니다. 동일한 이유로 rigt = mid하여 탐색 범위를 mid를 포함한 왼쪽 절반으로 줄입니다.
4. left < right 를 만족하지 못하기 때문에 탐색을 종료하고 left 또는 right 포인터를 반환합니다.
   • LowerBound(11)의 값은 5번 인덱스가 됩니다.

이번에는 LowerBound(3)를 구해보겠습니다. 가장 먼저 left, right 를 각각 0, 8로 설정합니다.

1. 중간 지점을 계산합니다. (left + right) // 2 = 4
   • 중간 값 10은 탐색 대상 3보다 크므로 정답 후보가 될 수 있습니다. 이는 정답 후보들이 mid를 포함한 왼쪽에 있다는 것을 의미합니다. 따라서 rigt = mid하여 탐색 범위를 mid를 포함한 왼쪽 절반으로 줄입니다.
2. 다시 중간 지점을 계산합니다.
   • 중간 값 5는 탐색 대상 3보다 크므로 정답 후보가 될 수 있습니다. 동일한 이유로 rigt = mid하여 탐색 범위를 mid를 포함한 왼쪽 절반으로 줄입니다.
3. 다시 중간 지점을 계산합니다.
   • 중간 값 4는 탐색 대상 3보다 크므로 정답 후보가 될 수 있습니다. 동일한 이유로 rigt = mid하여 탐색 범위를 mid를 포함한 왼쪽 절반으로 줄입니다.
4. 다시 중간 지점을 계산합니다.
   • 중간 값 2는 탐색 대상 3보다 작으므로 정답 후보가 될 수 없습니다. 이는 정답 후보들이 최소한 mid보다 오른쪽 있다는 것을 의미합니다. 따라서 left = mid + 1하여 탐색 범위를 오른쪽 절반으로 줄입니다.
5. left < right 를 만족하지 못하기 때문에 탐색을 종료하고 left 또는 right 포인터를 반환합니다.
   • LowerBound(3)의 값은 1번 인덱스가 됩니다.

이번에는 LowerBound(100)를 구해보겠습니다. 가장 먼저 left, right 를 각각 0, 8로 설정합니다.

1. 중간 지점을 계산합니다. (left + right) // 2 = 4
   • 중간 값 10은 탐색 대상 100보다 작으므로 정답 후보가 될 수 없습니다. 이는 정답 후보들이 최소한 mid보다 오른쪽 있다는 것을 의미합니다. 따라서 left = mid + 1하여 탐색 범위를 오른쪽 절반으로 줄입니다.
2. 다시 중간 지점을 계산합니다.
   • 중간 값 14는 탐색 대상 100보다 작으므로 정답 후보가 될 수 없습니다. 동일한 이유로 left = mid + 1하여 탐색 범위를 오른쪽 절반으로 줄입니다.
3. 다시 중간 지점을 계산합니다.
   • 중간 값 16는 탐색 대상 100보다 작으므로 정답 후보가 될 수 없습니다. 동일한 이유로 left = mid + 1하여 탐색 범위를 오른쪽 절반으로 줄입니다.
4. left < right 를 만족하지 못하기 때문에 탐색을 종료하고 left 또는 right 포인터를 반환합니다.
   • LowerBound(100)의 값은 8번 인덱스가 됩니다.

Upper Bound

Upper Bound Search는 찾고자 하는 값보다 큰 값 중에서 가장 작은 값의 위치를 반환하는 이분 탐색 방법입니다. 즉, target < arr[i]을 만족하는 최소 인덱스를 구할 수 있습니다.

1. 시작 인덱스 left와 끝 인덱스 right를 설정합니다. 이때 right = len(arr)로 설정합니다.
2. 중간 지점 mid = (left + right) // 2를 계산합니다.
3. arr[mid]와 target을 비교해 탐색 범위를 반으로 줄입니다.
   • target < arr[mid]인 경우: mid는 정답 후보일 수 있으므로 right = mid로 이동합니다.
   • target >= arr[mid]인 경우: mid는 정답이 될 수 없으므로 left = mid + 1로 이동합니다.
4. 2,3 과정을 left < right인 동안 반복합니다.
5. 반복 종료 시 left 또는 right가 Lower Bound 결과를 가리킵니다.

left < right 동안 반복하는 이유, right = mid가 되는 이유, 초기 right = len(arr)로 설정하는 이유는 Lower Bound 와 동일합니다.

정렬된 데이터를 기반으로 UpperBound(10)을 구해보겠습니다. 가장 먼저 left, right 를 각각 0, 8로 설정합니다.

1. 중간 지점을 계산합니다. (left + right) // 2 = 4
   • 중간 값 10은 탐색 대상 10보다 크지 않으므로 정답 후보가 될 수 없습니다. 이는 정답 후보들이 최소한 mid보다 오른쪽 있다는 것을 의미합니다. 따라서 left = mid + 1하여 탐색 범위를 오른쪽 절반으로 줄입니다.
2. 다시 중간 지점을 계산합니다.
   • 중간 값 14는 10보다 크므로 정답 후보가 될 수 있습니다. 따라서 정답 후보들은 mid 를 포함한 왼쪽에 있다는 것을 알 수 있습니다. 따라서 right = mid하여 탐색 범위를 mid를 포함한 왼쪽 절반으로 줄입니다.
3. 다시 중간 지점을 계산합니다.
   • 중간 값 12는 10보다 크므로 정답이 될 수 있습니다. 동일한 이유로 right = mid하여 탐색 범위를 mid를 포함한 왼쪽 절반으로 줄입니다.
4. left < right 를 만족하지 못하기 때문에 탐색을 종료하고 left 또는 right 포인터를 반환합니다.
   • UpperBound(11)의 값은 5번 인덱스가 됩니다.

이번에는 UpperBound(9)로 구해보겠습니다. 가장 먼저 left, right 를 각각 0, 8로 설정합니다.

1. 중간 지점을 계산합니다. (left + right) // 2 = 4
   • 중간 값 10은 9보다 크므로 정답 후보가 될 수 있습니다. right = mid 하여 탐색 범위를 mid를 포함한 왼쪽 절반으로 줄입니다.
2. 다시 중간 지점을 계산합니다.
   • 중간 값 5는 9보다 작으므로 정답 후보가 될 수 없습니다. 이는 정답 후보들이 최소한 mid보다 오른쪽 있다는 것을 의미합니다. 따라서 left = mid + 1하여 탐색 범위를 오른쪽 절반으로 줄입니다.
3. 다시 중간 지점을 계산합니다.
   • 중간 값 6은 9보다 작으므로 정답 후보가 될 수 없습니다. 동일한 이유로 left = mid + 1하여 탐색 범위를 오른쪽 절반으로 줄입니다.
4. left < right 를 만족하지 못하기 때문에 탐색을 종료하고 left 또는 right 포인터를 반환합니다.
   • UpperBound(9)의 값은 4번 인덱스가 됩니다.

이번에는 UpperBound(100)로 구해보겠습니다. 가장 먼저 left, right 를 각각 0, 8로 설정합니다.

1. 중간 지점을 계산합니다. (left + right) // 2 = 4
   • 중간 값 10은 100보다 작으므로 정답 후보가 될 수 없습니다. 이는 정답 후보들이 최소한 mid보다 오른쪽 있다는 것을 의미합니다. 따라서 left = mid + 1하여 탐색 범위를 오른쪽 절반으로 줄입니다.
2. 다시 중간 지점을 계산합니다.
   • 중간 값 14는 100보다 작으므로 정답이 될 수 없습니다. 동일한 이유로 left = mid + 1하여 탐색 범위를 오른쪽 절반으로 줄입니다.
3. 다시 중간 지점을 계산합니다.
   • 중간 값 16은 100보다 작으므로 정답이 될 수 없습니다. 동일한 이유로 left = mid + 1하여 탐색 범위를 오른쪽 절반으로 줄입니다.
4. left < right 를 만족하지 못하기 때문에 탐색을 종료하고 left 또는 right 포인터를 반환합니다.
   • UpperBound(100)의 값은 8번 인덱스가 됩니다.

Implementation

def binary_search(arr, target):  
    arr.sort()  
    left, right = 0, len(arr) - 1  
    while left <= right:  
        mid = (left + right) // 2  
        if arr[mid] == target:  
            return mid  
  
        if arr[mid] < target:  
            left = mid + 1      # mid 를 포함하지 않은 오른쪽 절반을 탐색.  
        else:  
            right = mid - 1     # mid 를 포함하지 않은 왼쪽 절반을 탐색.  
  
    return -1  
  
arr = [6, 16, 2, 10, 4, 5, 12, 14]  
print(binary_search(arr, 5))  
print(binary_search(arr, 14))  
print(binary_search(arr, 11))  
  
  
def lower_bound(arr, target):  
    arr.sort()  
    left, right = 0, len(arr)  
    while left < right:  
        mid = (left + right) // 2  
        if arr[mid] >= target:  # 정답 후보가 될 수 있으면(target이 arr[mid]보다 크거나 같으면)  
            right = mid         # mid 를 포함한 왼쪽 절반을 탐색.  
        else:  
            left = mid + 1      # mid 를 포함하지 않은 왼쪽 절반을 탐색.  
  
    return -1 if right == len(arr) else arr[right]  
  
arr = [2,4,5,6,10,12,14,16]  
print(lower_bound(arr, 11))  
print(lower_bound(arr, 3))  
print(lower_bound(arr, 100))  
  
  
def upper_bound(arr, target):  
    arr.sort()  
    left, right = 0, len(arr)  
    while left < right:  
        mid = (left + right) // 2  
        if arr[mid] > target:   # 정답 후보가 될 수 있으면(target이 arr[mid]보다 크면)  
            right = mid         # mid 를 포함한 왼쪽 절반을 탐색.  
        else:  
            left = mid + 1      # mid 를 포함하지 않은 왼쪽 절반을 탐색.  
  
    return -1 if right == len(arr) else arr[right]  
  
arr = [2,4,5,6,10,12,14,16]  
print(upper_bound(arr, 10))  
print(upper_bound(arr, 9))  
print(upper_bound(arr, 100))