이분 탐색

이분 탐색(Binary Search)이란?

이분 탐색은 정렬된 리스트에 대해 탐색 공간을 절반씩 줄여가며 특정한 값을 찾는 알고리즘이다.

탐색 공간을 절반씩 줄여가며 찾는다는 특유의 방식 덕분에

이분 탐색은 리스트의 크기가 굉장히 크거나 탐색 범위가 매우 넓을 때 사용하기 좋은 알고리즘이다.

변수의 범위가 제한조건에서 굉장히 넓게 제시돼있을 때
완전 탐색으로 해를 구할 수는 있지만 시간초과가 발생할 때

다만 여기서 중요한 건

반드시 정렬 혹은 단조 증가/감소가 보장되어야 한다는 점이다.

정렬된 자료
단조성 함수

💡 정렬된 자료가 필요한것은 이해하겠는데 단조성 함수는 뭘까?

단조성이란 “함수나 배열이 한 방향으로만 (증가하거나 감소하도록) 변한다”는 성질을 가리킨다.

물론 아직 잘 와닿지 않을테니 우선 천천히 실제 알고리즘 풀이 유형을 보면서 알아가보자.

이분 탐색 알고리즘 유형

이분 탐색 알고리즘 문제는 크게 두 가지로 나눌 수 있다.

정렬된 리스트에서 특정값이 있는지 체크
Parametric Search

이분 탐색 유형 1

간단하게 어떤 정렬된 리스트에서 특정값이 있는지를 이분 탐색을 사용해 검사한다 해보자.

이분 탐색은 기본적으로 아래의 흐름에 따라 탐색을 진행하게 된다.

리스트의 시작점 left와 끝점 right를 통해 중간값 mid를 설정

arr:  [0, 1, 2, 3, 4, 5, 6, 7]

target = 5
l = 0
r = 7
mid = (l+r)//2 = 3

arr[mid]를 target과 비교

arr:  [0, 1, 2, 3, 4, 5, 6, 7]
       l        ^     t     r
 
비교 : 3 = arr[mid] < target = 5

arr[mid]가 target보다 작으므로 오른쪽 범위를 탐색해야할 필요가 있음
```
기존 arr:  [0, 1, 2, 3, 4, 5, 6, 7]
           l        ^     t     r
new 범위:              [4, 5, 6, 7]
											 l  ^     r
```
오른쪽 범위는 m+1부터 시작하므로 left = m+1로 변경하고 mid값을 새로 계산
루프를 돌며 탐색 범위를 조절해 나가 arr[mid]가 target과 같아지는 mid를 찾으면 return True
```
탐색 범위:              [4, 5, 6, 7]
											 l m=t    r
```

이를 코드로 구현해보면 아래와 같다.

# 주어진 리스트에서 target 체크
def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    # left ≤ right 범위 안에 target이 있으면 계속
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return True
        elif arr[mid] < target:
            left = mid + 1  # 오른쪽 절반에 target이 있다면 left를 늘림
        else:
            right = mid - 1 # 왼쪽 절반에 target이 있다면 right를 줄임
    return False

유형 1-2

💡 만약 유형 1에서 더 나아가 ”정렬된 리스트에서 특정값 n이 중복으로 여러 개 존재할 때 가장 왼쪽(혹은 오른쪽)에 있는 n의 위치” 를 구하는 문제 같은 경우는 어떻게 해결할까?

이는 유형 1에서

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

이 부분을 적절하게 수정해주면 된다.

즉, 리스트 내에서 특정값을 찾더라도 검사를 이어나가도록

if nums[mid] <= target:   
		ans = mid
		left = mid + 1
else:
		right = mid - 1

이런식으로 처리를 해주면 된다.

Parametric Search(매개변수 탐색)

Parametric Search은 이분 탐색을 사용하여 조건을 만족하는 최솟값/최댓값을 찾는 기법이다.

Parametric Search 흐름

mid 값으로 탐색 범위를 절반으로 줄여나간다는 기본 진행 과정은 이분 탐색과 비슷하다.

다만 Parametric Search 문제에서는

초기에 left와 right로 설정해야할 값이 단순히 리스트 시작점과 끝점이 아닌 경우가 존재하며, 또한 탐색 범위를 설정하기위해 중간 값 mid로 target과 비교를 하는 과정이 단순히 배열에서 인덱스로 arr[mid]를 얻는 정도의 수준으로는 해결되지 않기 때문에,

“판정 함수”에 mid 값을 매개변수로 넣어 문제 상황에 따른 여러 처리를 거친 후 판정 결과를 반환하고, 그 결과에 따라 탐색 범위를 설정하게 된다.

이 때 사용되는 판정 함수가 바로 “단조성 함수”이다.

판정 함수 f(x)가 단조성 함수일 때

True 혹은 False 중 하나를 반환
x가 증가함에 따라 판정 결과가 딱 한 번만 바뀌는(T ↔ F) 단조성 확보
판정 결과가 바뀌는 지점이 바로 판정 조건의 최댓값 혹은 최솟값

즉, 이분 탐색이 값의 존재 여부를 찾는다면, Parametric Search은 조건이 바뀌는 지점(최솟값/최댓값)을 찾는다는 것이다.

즉, 아래와 같은 형태로 코드를 짜게 된다.

def func(mid, params...):
	# 매개변수들로 적절한 처리 후 True 혹은 False 리턴
	return True #(혹은 False)
	
left = ? 
right = ?

while left <= right:
		mid = (left + right) // 2
    if func(mid): 
    
        left = mid + 1  # 판정 함수가 T일 시 다음 루프 우측 탐색 진행
    else:
        right = mid - 1 # 판정 함수가 F일 시 다음 루프 시 좌측 탐색 진행