이진 탐색 개념

순차 탐색

가장 기본적인 탐색 방법이다. 리스트 안의 특정 데이터를 찾기 위해 앞에서부터 하나씩 확인해나간다. 데이터가 정렬되어 있지 않을 때 사용한다.

#p187 순차탐색

def sequencial(array, target, n):
    for i in range(n):
        if target == array[i]:
            return i + 1 #원하는 원소를 찾으면 그 원소의 위치를 반환

리스트의 개수가 N일 때, 최악의 경우 시간 복잡도는 O(N)이다.

이진 탐색

이진 탐색은 리스트의 데이터가 정렬되어 있을 경우에만 사용할 수 있는 알고리즘이다. 이미 정렬되어 있다면 매우 빠른 속도로 서치할 수 있다.

이진 탐색에서는 시작점, 끝점, 중간점 세 개의 위치 변수를 사용하는데, 목표 데이터와 중간점 위치의 데이터를 반복적으로 비교해서 목표 데이터를 찾는다.

한 번 탐색할 때마다 탐색할 데이터가 절반씩 줄어들기 때문에 시간 복잡도는 O(logN)이다. 순차 탐색보다 훨씬 줄어들었다.

코테에서는 주로 이진 탐색 문제가 나오면 탐색 범위가 큰 상황을 가정하는 경우가 많다고 한다. 그러므로 탐색 범위가 2000만을 넘어가면 이진 탐색을 사용해보자. 특히 처리해야 할 데이터의 개수나 값이 1000만 단위를 넘어가면 O(logN)의 속도를 가지는 알고리즘을 사용해야 한다.

재귀함수로 구현

한 번 직접 재귀함수로 구현해보았다.

#p188 이진탐색 - 재귀 활용

def binary_search(start, target, end, array):
    
    if start > end:
        return '원소 없음'
    
    median = (start + end) // 2
    alt_start = start
    alt_end = end

    if array[median] == target:
        return median
    
    if array[median] < target:
        alt_start = median + 1
    elif array[median] > target:
        alt_end = median - 1
        
    return binary_search(alt_start, target, alt_end, array)

a = [i for i in range(1, 20, 2)]
binary_search(0, 7, len(a) - 1, a)

교재에서는 구현이 어렵다고 겁을 줬는데, 막상 해보니 이상하게 많이 어렵지는 않았다. 다만 처음에 구현했을 때 binary_search(alt_start, target, alt_end, array)를 return을 안 붙이고 입력했더니 계속 함수의 리턴 값이 None이 나와버려서 약간 헤맸었다. 재귀함수 구현시에는 이 부분을 좀 생각해야 되는데 구현이 아직 익숙하지가 않은 것 같다.

반복문으로 구현

#이진탐색 - 반복문으로 구현
def binary_search(start, target, end, array):
    
    while True:
        if start > end:
            return '원소 없음'
    
        median = (start + end) // 2
        
        if array[median] == target:
            return median

        if array[median] < target:
            start = median + 1
        elif array[median] > target:
            end = median - 1
        

a = [i for i in range(1, 20, 2)]
binary_search(0, 7, len(a) - 1, a)

이건 위에서 재귀함수로 구현한 내용을 조금만 다듬으면 됐다.

데이터 빠르게 입력받기

입력 데이터의 개수가 1000만 개를 넘어갈 경우, 원래 하던대로 input()을 사용하면 시간 초과될 확률이 높다. 이 때는 sys 라이브러리의 readline()함수를 사용하면 된다고 한다.

import sys

input_data = sys.stdin.readline().rstrip()

readline()은 입력 후 '\n'이 추가되기 때문에 rstrip으로 이를 없애주어야 한다. 그냥 외워서 사용하자.