📚이진 탐색(Binary Search)이란?

이진 탐색은 탐색의 범위를 절반씩 좁혀가며 데이터를 빠르게 찾기 위한 탐색 방법이다. 이 알고리즘은 리스트의 중간값을 선택하여 찾고자 하는 값과 비교한다. 만약 중간값이 찾고자 하는 값보다 크다면 리스트의 왼쪽 절반을 다시 탐색하고, 중간값이 찾고자 하는 값보다 작다면 리스트의 오른쪽 절반을 다시 탐색한다. 이 과정을 반복하여 원하는 값을 찾는다.
이진 탐색은 리스트의 크기가 크거나 탐색 범위가 넓을 때 유용한 알고리즘이다.

한 과정을 거칠 때마다 탐색하는 범위가 절반씩 줄어드므로 시간 복잡도는 O(log N)를 가지게 된다.

이진 탐색 알고리즘을 사용할 때 주의할 점은 반드시 오름차순으로 정렬되어 있어야 사용이 가능하다.

⚒️동작 과정

1. 시작 인덱스(st)와 마지막 인덱스(ed) 사이의 중간 인덱스(mid)를 찾는다.
2. 중간 인덱스에 해당하는 값과 찾고자 하는 값이 같은지 비교한다.
3. 중간 인덱스에 해당하는 값이 더 크면 마지막 인덱스를 중간 인덱스-1(mid-1)해서 앞으로 한 칸 옮긴다.
4. 중간 인덱스에 해당하는 값이 더 작으면 시작 인덱스를 중간 인덱스+1(mid+1)해서 뒤로 한 칸 옮긴다.
5. 찾고자 하는 값과 중간 인덱스에 해당하는 값이 같아질 때까지 2~4번 과정을 반복한다.

✅파이썬 코드

arr = [1,3,5,6,8,11,13,15] # 정렬되어 있는 리스트
target = int(input())
def binary_search(st,ed,target): # 시작점, 끝점, 찾을 값
    while 1:
        mid = (st+ed)//2
        if arr[mid] == target:
            return 1
        elif arr[mid] > target:
            ed = mid - 1
        elif arr[mid] < target:
            st = mid + 1
        if ed < st:
            return 0
answer = binary_search(0,len(arr)-1,target)
if answer:
    print('원하는 값 찾음')
else:
    print('원하는 값 못 찾음')

📗파라메트릭 서치(Parametric Search)

이분탐색 알고리즘을 이야기할 때 함께 나오는 탐색 방법인 Parametric Search는 이분탐색과 상당히 유사하다.

파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 풀어 나가는 기법이다. 여기서 결정 문제란 'yes' or 'no', 즉, '예' 또는 '아니오'로 답하는 문제를 말한다. 파라메트릭 서치는 주로 특정 조건을 만족하면서 동시에 가장 적합한 변숫값을 찾아나가는 문제에서 활용되며, 이진 탐색(Binary Search)을 이용하여 구현한다. 예를 들어, 특정 조건을 만족하는 가장 큰 값을 구하는 최적화 문제에서 이진 탐색을 통해 적합한 해(solution)의 범위를 절반씩 좁혀 나갈 수 있다.

Parametric Search 적용 문제

1. 배터리가 몇% 충전 되어 있는지 O(n)보다 빠르게 검색

battery = ['*','*','*','*','*','*','_','_','_','_']
#battery = '******____'
def parametric_search(st,ed):
    maxvalue = -1
    while 1:
        mid = (st+ed) // 2
        if battery[mid] == '*':
            maxvalue = mid
            st = mid + 1
        elif battery[mid] == '_':
            ed = mid - 1
        if st > ed:
            break
    return maxvalue + 1
answer = parametric_search(0,len(battery)-1)
print(f'{answer}0%')

2. 커서의 위치를 알려주는 프로그램 (O(n)보다 빠름)

6*10 size 리스트
curser=[
 '##########',
 '##########',
 '###_______',
 '__________',
 '__________',
 '__________',
]
def curser_search1(st,ed): # 세로 검사
    maxi = 0
    while 1:
        mid = (st+ed) // 2
        if curser[mid][0] == '#':
            maxi = mid
            st = mid + 1
        elif curser[mid][0] == '_':
            ed = mid - 1
        if st > ed:
            break
        return maxi
def curser_search2(st,ed,yy): 
# yy는 curser_search1에서 찾은 y좌표
    maxj = 0
    while 1:
        mid = (st+ed) // 2
        if curser[yy][mid] == '#':
            maxj = mid
            st = mid + 1
        elif curser[yy][mid] == '_':
            ed = mid - 1
        if st > ed:
            break
        return maxj
answer1 = curser_search1(0,5)
answer2 = curser_search2(0,9,answer1-1)
print(answer1,answer2)

참고 블로그
[Python] 이분탐색 쉽게 푸는 템플릿
[알고리즘] 파라메트릭 서치(Parametric Search)에 대해 알아보자!