[알고리즘] 이진 탐색(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과 비교한다.

1. 중간점 == target이면 탐색을 종료한다.
2. 중간점 > target이면 중간점 왼쪽의 배열에 대해 다시 탐색한다.
3. 중간점 < 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 파이썬』, 나동빈 지음