Chapter 7. 이진 탐색

이진 탐색

이진 탐색을 사용하면 리스트 내에서 데이터를 매우 빠르게 탐색할 수 있다. 이진 탐색에 대해 알아보기 전에 가장 기본 탐색 방법인 순차 탐색에 대해 먼저 이해할 필요가 있다.

• 순차 탐색 : 리스트 내의 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
  
  • 데이터의 정렬 여부와 관계없이 가장 앞에 있는 원소부터 하나씩 확인
  • 데이터의 개수가 N개일 때, 최대 N번의 비교 연산이 필요하므로 시간 복잡도는 O(N)

개념 정리

이진 탐색

• 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
  
  • 필요한 변수 : 시작점, 끝점, 중간점
  • 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교
• 단계마다 2로 나누는 것과 동일하므로 시간 복잡도는 O(logN)

예시 : 값이 4인 카드 탐색

1. 시작점[0], 끝점[9], 중간점[4] : 중간점[4]의 수 8과 찾으려는 수 4를 비교
   • 중간점[4]의 수 8이 더 크므로 중간점[4] 이후의 값은 확인할 필요가 없음
   • 끝점[9]을 중간점[4]의 이전인 [3]으로 옮김
2. 시작점[0], 끝점[3], 중간점[1] : 중간점[1]의 수 2와 찾으려는 수 4를 비교
   • 중간점[1]의 수 2가 더 작으므로 이번에는 값이 2 이하인 수는 확인할 필요가 없음
   • 시작점[0]을 중간점[1]의 다음인 [2]로 옮김
3. 시작점[2], 끝점[3], 중간점[2] : 중간점[2]의 수 4와 찾으려는 수 4를 비교
   • 중간점[2]의 수와 찾으려는 수가 동일하므로 탐색 종료

재귀 코드

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)

트리 자료구조

이진 탐색은 전제 조건이 데이터 정렬이다. 데이터 베이스는 내부적으로 대용량 데이터 처리에 적합한 트리 자료구조를 이용해 항상 데이터가 정렬돼 있다. 데이터베이스의 탐색은 이진 탐색과는 조금 다르지만, 유사한 방식으로 탐색을 항상 빠르게 수행하도록 설계되어 있다.

트리

• 노드와 노드의 연결로 표현하며, 노드는 정보의 단위로서 정보를 가지고 있는 개체로 이해할 수 있음
• 특징
  • 트리는 부모 노드와 자식 노드의 관계로 표현
  • 트리의 최상단 노드는 루트 노드
  • 트리의 최하단 노드는 단말 노드
  • 트리의 일부를 떼어내도 트리 구조이며, 서브 트리라 부름
  • 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기 적합

트리

이진 탐색 트리

• 이진 탐색 트리 조건 : 왼쪽 자식 노드 < 부모 노드  < 오른쪽 자식 노드
  
  • 부모 노드보다 왼쪽 노드가 작음
  • 부모 노드보다 오른쪽 자식 노드가 큼

• 예시 : 값이 37인 노드 탐색
  1. 루트 노드부터 방문 : 루트 노드의 값 (30)보다 찾는 값 (37)이 크므로 왼쪽 노드를 확인할 필요가 없음
  2. 오른쪽 노드 방문 : 오른쪽 노드 (48)보다 찾는 값(37)이 작으므로 오른쪽 노드를 확인할 필요가 없음
  3. 왼쪽 노드 방문 : 왼쪽 노드 (37)과 찾는 값 (37)이 같으므로 탐색 종료

이진 탐색 트리

TIP : 빠르게 입력받기

이진 탐색 문제는 입력 데이터가 많거나 탐색 범위가 매우 넓은 편이다. 입력 데이터의 개수가 많은 문제에 input() 함수를 사용하면 동작 속도가 느려서 시간 초과로 오답 판정을 받을 수 있다. 이처럼 입력 데이터가 많은 문제는 sys 라이브러리 readline() 함수를 이용하면 시간 초과를 피할 수 있다.

예제 코드

import sys
input = sys.stdin.readline

input_data = input().rstrip()
print(input_data)