이진 탐색 알고리즘은 정렬된 데이터에서 원하는 값을 빠르게 찾을 수 있는 탐색 알고리즘이다. 먼저 기본적인 순차탐색에 대해 알아보자

순차 탐색

리스트 안의 특정 데이터를 찾기 위해서 앞에서부터 하나씩 차례대로 확인하는 방법이다. 정석대로 for문을 돌며 각 원소를 돌며 원하는 값을 찾는 것이다. 순차 탐색은 정렬 여부와 관계없이 값을 찾을 수 있고, 하나씩 확인하기 때문에 주어진 데이터의 크기가 N이라면, $O(N)$의 시간 복잡도를 가진다.

def sequential_search(n,target,array):
    for i in range(n):
        if array[i]==target:
            return i+1
        


array=[2,3,4,5,1,8,4,9,2,3,4,5]
target=9
print(sequential_search(len(array),target,array))

위는 간단하게 array를 탐색하여 target값 9의 위치를 반환하는 함수이다. 실제로, 리스트 자료형에서 특정한 값을 가지는 원소의 갯수를 세는 count() 메서드가 바로 이 순차탐색을 기반으로 수행한다.

순차탐색 알고리즘은 무조건 데이터의 크기만큼의 시간복잡도를 가진다는 특징이 있다.

이진 탐색

이진 탐색 알고리즘은 정렬된 데이터에만 적용할 수 있다. 데이터에서 시작점,중간점,끝점을 가리키는 변수를 사용하고, 찾으려는 데이터와 중간점 위치의 데이터를 반복적으로 비교하여 원하는 데이터를 찾는다. 다음은, 이진 탐색이 이루어지는 과정이다.

탐색할 원소가 반씩 계속 줄어들기 때문에 $O(logN)$의 시간 복잡도를 가진다. python으로 재귀함수나, 반복문을 사용해 구현할 수 있다. (위의 그림에서 각 위치 변수밑에 적힌 숫자는 리스트에서의 인덱스를 의미한다)

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

def binary_search(array,target,start,end):
    # 찾는 데이터가 존재하지 않을 경우.
    # start index가 end index보다 크면 값은 존재하지않는다는 뜻.
    if start>end:
        return None
    mid=(start+end)//2 # mid index (소수점 이하는 버림)

    if array[mid]==target:
        return mid # target값 찾으면 index return
    
    elif array[mid]>target:
        return binary_search(array,target,start,mid-1) # mid값이 target보다 크면, end index mid-1 위치로 하여 재탐색
    
    else:
        return binary_search(array,target,mid+1,end)
    
n,target=map(int,input().split())
array=list(map(int,input().split()))
print(array)
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=map(int,input().split())
array=list(map(int,input().split()))
print(array)
result=binary_search(array,target,0,n-1)

if result==None:
    print("존재하지않는 원소에 대한 탐색 요청이었음")
else:
    print(result+1)

재귀함수에서 start값이 end보다 큰 경우 None을 return하고 종료되는데, while문을 통해 start값이 end보다 작거나 같은 동안 반복문을 수행하며, 실제 cursor에 해당하는 start,end,mid 값만 이동하게끔 mid 데이터와 target 데이터의 대소비교를 통해 구현하는 것으로 모두 같은 실행결과를 가진다.

빠르게 입력받기

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

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

sys 라이브러리를 사용할 때, 한 줄 입력받고 나서 rstrip() 함수를 꼭 호출해야한다. readline() 메서드로 엔터가 줄 바꿈 기호로 입력되기 때문이다. 이 공백 문자를 제거하려면 rstrip() 함수를 사용해야한다.