[알고리즘] 이진 탐색(Binary Search)

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

이진 탐색은 정렬되어 있는 배열 내부의 데이터를 탐색하여 원하는 데이터를 빠르게 찾기위해 사용하는 알고리즘이다. 이 알고리즘의 특징은 아래와 같다.

정렬된 형태라면 매우 빠르게 데이터를 찾을 수 있다.
탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다.

이진 탐색 과정에서는 시작점, 끝점, 중간점으로 배열 내 데이터의 위치를 나타내며, 찾으려는 target 데이터와 중간점의 값을 반복적으로 비교하면서 범위를 절반으로 좁혀나간다.

예를 들어, 다음과 같은 배열이 있다.

array=[0,1,3,5,8,9]

데이터의 위치는 index로 표현한다.시작점은 index 0이고, 끝점은 index 5이다.이 때, 중간점은 시작 + 끝 // 2 의 값이다. 즉, 중간점이 실수이면 소수점 이하를 버린 값의 index가 중간점이 된다. 따라서 중간점은 index2이다.

이 때, target이 5라면, 중간점의 값 array[2]==3과 비교한다.

중간점 == target이면 탐색을 종료한다.
중간점 > target이면 중간점 왼쪽의 배열에 대해 다시 탐색한다.
중간점 < target이면 중간점 오른쪽의 배열에 대해 다시 탐색한다.

위의 규칙에 따라 target이 중간점값 보다 크므로 중간점==2보다 오른쪽의 배열에 대해 index 3부터 탐색을 진행하면 된다.

👨🏻‍💻 Code

이진 탐색은 재귀함수와 **반복문 **형태 두가지로 구현할 수 있다.

재귀함수로 구현

# 재귀함수로 구현한 이진탐색
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)

반복문으로 구현

#반복문으로 구현한 이진탐색
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start+end)//2
        # 찾은 경우, 중간점 인덱스 반환
        if array[mid] == target:
            return mid
        # 중간점 값이 target보다 큰 경우
        elif array[mid] >target:
            end = mid - 1
        # 중간점 값이 target보다 작은 경우
        else:
            start = mid + 1
    return None

시간복잡도

이진 탐색은 한 번 확인할 때마다 확인하는 원소 개수가 절반씩 감소한다. 따라서, 시간 복잡도는 O(logN)에 해당한다. O(N)의 순차 탐색과 비교할 때, 데이터의 개수가 많을 경우 훨씬 빠르게 데이터를 찾을 수 있다는 장점이 있다.

🍯 Tip

이진 탐색은 코딩테스트에 자주 등장하니 외워두면 좋다.
마찬가지로, 코딩테스트에서 데이터 개수가 1,000만 단위 이상으로 커질 경우, 이진 탐색 알고리즘을 고려하는 것이 좋다. 이진 탐색을 통해 빠르게 탐색하지 않을 경우, 시간 초과 될 수 있다.
입력 데이터가 많은 경우 => sys라이브러리를 사용!
- 이진 탐색 문제의 경우, 입력 데이터가 많은 경우가 있다. 이 때, sys.readline()을 사용하면 빠르게 데이터를 입력받아 시간초과를 피할 수 있다.

import sys
input_line = sys.stdin.readline().rstrip()
# readline()을 통해 한줄의 문자열을 읽는다. 줄바꿈을 '\n'으로 인식하므로, rstrip()으로 제거해준다.

📚 Reference

이 글은 『이것이 코딩테스트다 with 파이썬』, 나동빈 지음 을 공부하며 기록한 글입니다.

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