[파이썬][알고리즘] 이진 탐색

이진 탐색 (Binary Search)

• 자료를 둘로 나누어 탐색하는 방법이다.
  • 숫자가 정렬되어있는 상태여야 한다.
  • 중간부터 시작하여 그 수보다 큰 쪽에 있는지 작은 쪽에 있는지 확인한다.
  • 이를 반복하여 찾아 나간다.

분할 정복과 이진 탐색

• 분할 정복 알고리즘 (Divide and Conquer)
  • Divide: 문제를 나눈다.
  • Conquer: 문제가 작고 해결 가능하면 해결하고 아니면 다시 나눈다.
• 이진 탐색
  • Divde: 리스트를 두개로 나눈다.
  • Conquer
    • 중간값 보다 크면 큰 부분에서 검색할 숫자를 찾는다.
    • 중간값보다 작으면 작은 부분에서 검색할 숫자를 찾는다.

알고리즘 구현

def binary_search(num_list, value):
    print(num_list)
    if len(num_list) == 1 and value == num_list[0]:
        return True

    if len(num_list) == 1 and value != num_list[0]:
        return False

    if len(num_list) == 0:
        return False

    mid = len(num_list) // 2

    if value == num_list[mid]:
        return True
    else:
        if value > num_list[mid]:
            return binary_search(num_list[mid:], value)
        else:
            return binary_search(num_list[:mid], value)

import random

num = random.sample(range(100), 10)
num

[65, 97, 66, 13, 27, 92, 55, 84, 62, 25]

num.sort()

num

[13, 25, 27, 55, 62, 65, 66, 84, 92, 97]

binary_search(num, 92)

[13, 25, 27, 55, 62, 65, 66, 84, 92, 97]
[65, 66, 84, 92, 97]
[84, 92, 97]





True

binary_search(num, 60)

[13, 25, 27, 55, 62, 65, 66, 84, 92, 97]
[13, 25, 27, 55, 62]
[27, 55, 62]
[55, 62]
[55]





False

시간 복잡도

• 한번 진행할 때마다 비교해야 할 데이터가 1/2이 된다.
  • O($logn$)