6-1. [알고리즘 이론] 탐색 알고리즘 - 이진 탐색 -

Shy·2023년 8월 11일

자료구조 ＆ 알고리즘(Python)

목록 보기

19/24

이진 탐색

이진 탐색(Binary Search)은 정렬된 데이터셋에서 특정한 값을 효율적으로 찾기 위한 알고리즘이며, 분할 정복 전략을 사용하여 작동한다.

동작 원리

정렬된 리스트에서 중간 값(middle value)을 선택한다.
중간 값이 찾고자 하는 값(target value)과 같다면, 그 위치(index)를 반환한다.
찾고자 하는 값이 중간 값보다 크다면, 중간 값을 기준으로 오른쪽 하위 리스트에서 다시 탐색한다.
찾고자 하는 값이 중간 값보다 작다면, 중간 값을 기준으로 왼쪽 하위 리스트에서 다시 탐색한다.
리스트에 더 이상 검사할 요소가 없을 때까지 위의 과정을 반복한다.

이진 탐색의 특징

이진 탐색은 정렬된 데이터셋에서만 사용 가능하다.
탐색 범위를 절반씩 줄이기 때문에 O $(log n)$ 의 시간 복잡도를 갖습니다. 이는 매우 효율적인 탐색 방법이다.
그러나 리스트가 정렬되어 있지 않다면 정렬하는데 $O(n log n)$ 의 시간이 소요될 수 있으므로, 데이터셋이 이미 정렬된 상태인 경우에 가장 효과적이다

순차 탐색과 이진 탐색

분할 정복 알고리즘과 이진 탐색

분할 정복 알고리즘 (Divide and Conquer)
- Divide: 문제를 하나 또는 둘 이상으로 나눈다.
- Conquer: 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다.
이진 탐색
- Divide: 리스트를 두 개의 서브 리스트로 나눈다.
- Comquer
  - 검색할 숫자 (search) > 중간값 이면, 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다.
  - 검색할 숫자 (search) < 중간값 이면, 앞 부분의 서브 리스트에서 검색할 숫자를 찾는다.

Python 코드 예제

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0
 
    while low <= high:
 
        mid = (high + low) // 2
 
        # x가 mid 위치에 있으면 mid 반환
        if arr[mid] < x:
            low = mid + 1
 
        # x가 mid 위치에 있으면 mid 반환
        elif arr[mid] > x:
            high = mid - 1
 
        # x가 중간에 위치해 있을 때
        else:
            return mid
 
    # x가 리스트에 존재하지 않는 경우
    return -1

이진 탐색 구현해보기

정렬된 리스트의 중앙 값과 찾고자 하는 값을 비교한다.
찾고자 하는 값이 중앙 값보다 크면 리스트의 오른쪽 부분을, 작으면 왼쪽 부분을 대상으로 다시 탐색을 수행한다.
이 과정을 반복하여 원하는 값을 찾거나 탐색 범위가 없어질 때까지 계속한다.

주의사항

데이터셋은 반드시 정렬된 상태여야 합니다.
매 시도마다 탐색 범위가 절반으로 줄어들므로 O(log n)의 시간 복잡도를 갖는다.

코드

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0

    while low <= high:
        mid = (high + low) // 2

        # x가 mid 위치에 있다면 인덱스 반환
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid

    # x가 리스트에 없으면 -1 반환
    return -1

예

data = [1, 2, 3, 4, 5, 6, 7, 8, 9]
result = binary_search(data, 7)
if result != -1:
    print(f"Element found at index {result}")
else:
    print("Element not found in the list")