Advanced Algorithm - 이진 탐색(Binary Search)

1. 시작하기 전에 

- 아래와 같은 문제가 있을 때, 어떤 방법(=알고리즘)을 사용하는 것이 가장 효율이 좋을지 생각해보자. 

 

 

생각의 과정 

 

1. 조건 점검하기 

- 1~100 사이의 난수가 30개의 병뚜껑에 적혀있고 이 중에 70이 있는지 찾아야 한다.

- 30개의 병뚜껑에는 오름차순으로 숫자가 정렬되어 있다. 

- 가장 적은 수의 병을 따서 70을 찾아야 한다. 

 

2. 가장 적은 수의 병을 따는 방법  

- 1~30번 후보군의 중간에 위치한 15번 병뚜껑을 확인하여 후보군을 반으로 줄인다. 

- 15번 병뚜껑의 숫자가 70보다 작다면 우측(16 ~ 30번 병뚜껑), 70보다 크다면 좌측(1~14번 병뚜껑)을 후보군으로 선정한다. 

- 좌측 또는 우측의 후보군이 선정되면 위의 과정을 반복한다. 

- 최종적으로 숫자 70을 찾는다. 

 

→ 위에서 설명한 과정(=알고리즘)이 바로 이진 탐색이다. 그렇다면 이진 탐색이 무엇일까?

 

---

2. 이진 탐색이란?  

- 탐색할 자료를 둘로 나누어 찾는 데이터가 있을만한 곳을 탐색하는 방법 

 

 

이진 탐색의 동작 - 순차 탐색과 비교를 통한 이해 

 

https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

 

---

3. 분할 정복과 이진 탐색의 연관성  

 

a) 분할 정복(Divide & Conquer)

- 분할(Divide): 문제를 하나 또는 둘 이상으로 나눈다.

- 정복(Conquer): 나누어진 문제가 충분히 작고, 해결 가능한 크기라면 해결한다. 반대로, 충분히 작지 않다면 다시 분할한다. 

 

 

b) 이진 탐색(Binary Search)

- 분할(Divide): 주어진 자료(리스트)를 두 개의 서브리스트로 나눈다. 

- 정복(Conquer): 검색할 숫자 > 중간값 이라면, 리스트의 뒷부분에서 검색할 숫자를 찾는다. 반대로, 검색할 숫자 < 중간값 이라면, 리스트의 앞부분에서 검색할 숫자를 찾는다. 

 

---

4. 코드구현 

def binary_search(data, search): #search = 찾는 값
    
    if len(data) == 1 and search == data[0]: #마지막 검색값이 찾는 값인 경우 
        return True
    if len(data) == 1 and search != data[0]:#끝까지 검색했는데 찾는 값이 없는 경우 
        return False
    if len(data) == 0:
        return False
    
    median = len(data) // 2
    if search == data[median]:
        return True
    else:
        if search > data[median]: #찾는 값이 중간 값보다 크다면 
            return binary_search(data[median:], search) #뒤쪽 리스트 
        else: #찾는 값이 중간 값보다 작다면
            return binary_search(data[:median], search) #앞쪽 리스트 

 

 

[테스트 결과] 

---

5. 시간 복잡도

- 이진 탐색은 분할과 정복 과정을 이용하여 처리해야 할 데이터의 대상의 수가 50%씩 줄어든다. 

- 그러므로 이진 탐색의 경우의 수는 n x (0.5)^n 이며 연산 결과값이 1이 될 때까지 진행하게 된다. 

- 결론으로, 이진 탐색의 시간복잡도는 O(log n)이다.