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

Binary Search

• 정렬된 리스트에서 범위를 줄여가며 결과값을 찾는 알고리즘
• 정렬된 상태에서만 사용이 가능하지만 탐색할 때마다 탐색 범위가 줄기 때문에 속도가 빠름

---

직관

• Up & Down 게임 
  • 1 ~ 100 사이의 숫자라고 할 때 1 부터 추리하기보다는 50부터 추리하여 탐색 범위를 줄임

---

순차 탐색과 이진 탐색 비교

https://blog.penjee.com/5-gifs-to-understand-binary-search-tree/

---

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

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

---

구현

def binary_search(data_list, find_data):
    if len(data_list) == 1 and find_data == data_list[0]:
        return True
    if len(data_list) == 1 and find_data != data_list[0]:
        return False
    if len(data_list) == 0:
        return False
    
    medium = len(data_list)//2
    print(data_list)
    if find_data == data_list[medium]:
        return True
    else:
        if find_data > data_list[medium]:
            return binary_search(data_list[medium:], find_data)
        else:
            return binary_search(data_list[:medium], find_data)

import random

data_list = random.sample(range(100),10)
data_list.sort()
binary_search(data_list, 78)

[25, 34, 44, 46, 52, 65, 75, 76, 79, 81]
[65, 75, 76, 79, 81]
[76, 79, 81]
False

---

시간 복잡도

• n개의 list를 매번 2로 나누어 1일 될 때까지 비교 연산을 k회 진행함
  • \( n\times \frac{1}{2}\times \frac{1}{2}\times \frac{1}{2}\cdots =1 \)
  • \( n \times \frac{1}{2}^{k} = 1 \)
  • \( n = 2^{k}=log_{2}2^{k} \)
  • \( log_{2}n = k \)
  • O(\( logn \))