이진 탐색

이진 탐색 ( Binary Search )이란 정렬된 배열에서 타겟을 빠르게 찾는 검색 알고리즘이다.

• 제약 조건 : 정렬된 상태의 배열에서 사용가능
• 장점 : 시간복잡도가 O(logN) 으로 매우 빠른 성능 보유

시간복잡도를 수치로 변경하여 설명해보면 다음과 같다.

 

크기 1억개인 배열에서 특정 값을 찾는 경우. ( 정렬된 경우 )

• 순차 탐색 : 최악의 경우 1억번 탐색 필요
• 이진 탐색 : log100000000 번 탐색 필요. 대략 26번만의 탐색으로 특정 값을 찾을 수 있음

 

이를 Python 코드로 직접 구현하여 탐색 횟수를 비교해보자.

import random

# 1 - 천만
nums = [i for i in range(1, 10000001)]

# 유니크한 백만개의 수를 1-천만 범위에서 리스트로 추출
random_nums = random.sample(nums, 1000000)

# 첫번째 대상을 타겟으로 설정
target_num = random_nums[0]

# 정렬
random_nums.sort()

# 앞에서부터 순차적으로 검색
search_cnt = 0
for num in random_nums:
    if num == target_num:
        break
    search_cnt += 1


# Binary Search

def binary_search(start, end, target, arr, cnt):
    cnt += 1
    mid = (start + end) // 2
    if arr[mid] == target:
        return cnt

    if arr[mid] < target:
        start = mid + 1
        return binary_search(start, end, target, arr, cnt)

    if arr[mid] > target:
        end = mid - 1
        return binary_search(start, end, target, arr, cnt)


# BinarySearch로 검색
binary_search_cnt = binary_search(0, len(random_nums) - 1, target_num, random_nums, 0)

print(f"타겟. {target_num}")
print(f"순서대로 검색. {search_cnt}")
print(f"이진탐색으로 검색. {binary_search_cnt}")


""" 실행 결과

타겟. 4729121
순서대로 검색. 473282
이진탐색으로 검색. 20

"""