[CS기초] 이분 탐색(Binary Search)

이분 탐색 (Binary Search) 개요

이분 탐색은 정렬된 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법인데요. 이분 탐색을 수행하기 위해서는 다음 두 가지 조건을 만족해야 합니다.

• 주어진 배열이 반드시 정렬되어 있어야 한다.
• 무한 루프에 빠지지 않게 중간값을 잘 정해야 한다.

 

이분 탐색의 활용

이분 탐색을 진행하게 되면, 시작값과 끝값이 엇갈릴 때까지 배열의 중간값이 찾는 값과 맞는지 확인하게 됩니다.

 

이때 배열의 중간값이 찾는 값이라면 그 위치를 반환해줍니다. 그런데 같지 않고 배열의 중간값이 찾는 값보다 작다면 배열을 중간으로 나눴을 때의 오른쪽에 있다는 뜻이므로 시작값을 갱신해주고, 반대의 경우라면 끝값을 갱신해줍니다.

# 특정 값의 인덱스를 찾는 함수
def binary_search(arr, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return None
    
# 사용 예시
n = 4
arr = [1, 3, 7, 10]
print(binary_search(arr, 7, 0, n-1))    # 2 출력

 

 

이분 탐색 라이브러리 bisect

파이썬에는 이분 탐색을 손쉽게 할 수 있는 라이브러리를 제공해 주는데요. 바로 bisect 입니다. 해당 라이브러리에는 bisect_left, bisect_right 함수 등이 있어 위의 이분 탐색 활용 코드를 단 한 줄로 짤 수 있게 도와줍니다. 보통은 찾는 값과 같은 값의 위치를 반환해주는 bisec_left를 많이 사용합니다.

• bisect_left(arr, x) : 찾는 값과 같거나 큰 첫 위치를 반환하는 함수
• bisect_right(arr, x) : 찾는 값보다 큰 첫 위치를 반환하는 함수

# 특정 값의 위치 찾기
# 단, 찾고자 하는 값이 없는 경우 해당 값보다 큰 첫번째 위치를 반환하므로 주의
idx = bisect_left(arr, find)

 

그리고 bisect_left, bisec_right를 모두 활용하면 배열에서 해당 값의 개수를 구할 수도 있습니다.

# 값이 특정 범위에 속하는 원소의 개수를 구하는 함수
# left_value, right_value를 같게 하면 특정 원소의 개수를 구할 수도 있다
def cal_num(arr, left_value, right_value):
    return bisect_right(arr, right_value) - bisect_left(arr, left_value)

 

 

Parametric Search

조건을 만족하는 최솟값 또는 최댓값을 구하는 문제(최적화 문제)를 결정 문제로 변환해 이분탐색을 수행하는 방법

• 예시) 백준 2805번 나무 자르기
  • (최적화 문제) 나무 M미터를 얻을 수 있는 절단기에 설정할 수 있는 최대 높이 X
  • (결정 문제) 절단기에 설정한 높이가 X일때 얻을 나무가 M미터 이상인가, 미달인가?
• 단, 결정 문제로 얻은 함수가 증가함수 또는 감소함수여야 parametric search를 사용할 수 있다.
  • 위의 나무 자르기 문제에서, 절단기의 높이가 증가할수록 얻는 나무가 감소하므로 감소함수이다.
• 문제에서 최소/최대 언급이 있고 범위가 매우 크거나 시간복잡도 N 하나를 logN으로 떨어뜨리면 문제가 풀릴 것 같을 때 사용을 고려해 볼 수 있다.

parametric search의 풀이 과정

1. 시작값과 끝값을 정한 뒤, 중간값을 선택해 결정 문제 조건을 만족하는지 검사
   • 예시) 절단기의 최대 높이, 최소 높이를 정한 뒤, 두 높이를 반으로 나눈 중간 높이를 선택해 이 높이로 나무들을 잘랐을 때 나무를 M미터 이상 얻을 수 있는지 검사
2. 조건을 만족하는 경우, 해당 값을 일단 답으로 기록한 뒤 더 나은 답을 찾는 쪽으로 탐색 범위를 줄인다.
   • 최댓값 결정 문제인 경우 시작값을 중간값 + 1, 최솟값 결정 문제인 경우 끝값을 중간값 - 1로 설정한다.
   • 조건을 만족하지 않는 경우, 반대쪽으로 탐색 범위를 줄인다.
   • 예시) 절단기의 중간 높이에서 나무를 M미터 이상 얻은 경우, 일단 답으로 기록한 뒤 나무의 시작 높이를 중간값 + 1 로 설정해 다음 중간 높이가 더 높아지게 만든다.
     • 반대로 M미터 미만인 경우 나무의 끝 높이를 중간값 - 1로 설정해 다음 중간 높이가 더 낮아지게 만든다.
3. 시작값과 끝값이 엇갈릴 때까지 위 1, 2의 과정을 반복한다.