[#알고리즘/이진탐색]

🤷‍♀️ 이진 탐색이란?

이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용이 가능하다. 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있으며 탐색 범위를 절반씩 좁혀가며(O(logN)) 데이터를 탐색하는 특징이 있다.

이진 탐색은 위치를 나타내는 변수 3개를 사용한다.

• 탐색하고자 하는 범위의 시작점
• 탐색하고자 하는 범위의 끝점
• 탐색하고자 하는 범위의 중간점

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교한다.

✔ 재귀 함수로 구현한 이진 탐색

def binary_search(array, target, start, end) :
    if start > end :
        return None
    mid = (start + end) // 2
    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    else :
        return binary_search(array, target, mid + 1, end)
    
n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)
if result == None :
    print("원소가 존재하지 않음")
else :
    print(result + 1)

✔ 반복문으로 구현한 이진 탐색

def binary_search(array, target, start, end) :
    while start <= end :
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else : 
            start = mid + 1
    return None

n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)
if result == None :
    print("원소가 존재하지 않음")
else :
    print(result + 1)

이진 탐색은 언제 사용 ?

다량의 데이터를 검색하거나 탐색 범위가 1,000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN)의 속도를 내야 하는 알고리즘을 떠올려야 문제 해결이 가능하다.

👉 이진 탐색 트리

이진 탐색 트리는 다음과 같은 특징을 가진다.

• 부모 노드보다 왼쪽 자식 노드가 작다.
• 부모 노드보다 오른쪽 자식 노드가 크다.

즉, 왼쪽 자식 < 부모 < 오른쪽 자식이 성립해야 한다.

루트 노드부터 방문하여 찾는 원소값이 더 크면 오른쪽 노드를 방문하고 찾는 원소값이 더 작으면 왼쪽 노드를 방문한다.

이진 탐색 문제는 데이터 탐색 범위가 매우 넓기 때문에 sys 라이브러리의 readline() 함수를 사용한다.

import sys
data = sys.readline().rstrip()

참고로 rstrip() 함수는 줄 바꿈(Enter) 공백 문자를 제거해준다.

Reference
『이것이 코딩 테스트다 with 파이썬』, 나동빈 지음