[알고리즘] 분할 정복 - 이진 검색 (Divide and Conquer - Binary Search)

1. Binary Search의 알고리즘 및 코드

 

분할 정복의 기본은 재귀이기 때문에 반복문이 아닌 재귀를 통해서 binary search를 하겠습니다.

반복문을 통한 binary search는 앞 글을 참고해주세요.

 

Problem : 원소가 n개인 (오름차순)정렬된 리스트 S안에 검색하려는 수 x가 있는가?

input : 양의 정수 n, 정렬된 리스트 S, 검색키 x

output : x의 위치, 만약 없다면 -1를 반환

 

알고리즘 구상)

1) x와 S의 중간 값과 비교해 같다면 그대로 끝

2) 만약 다르다면 두 가지 방법을 이용한다.

    2.1) x가 S의 중간 값보다 작다면 중간 위치를 기준으로 왼쪽 리스트를 탐색한다.

    2.2) x가 S의 중간 값보다 크다면 중간 위치를 기준으로 오른쪽 리스트를 탐색한다.

3) subarray에서 1번과 2번을 반복한다. subarray가 크기가 너무 작아서 재귀를 쓸 수 없을 때까지 반복한다.

4) subarray에서 찾은 결과가 곧 문제의 결과이기 때문에 subarray의 답이 최종 답이다.

 

사실 이런거는 구상 이후에 손으로 한 번 직접 그려봐야하는데, 저는 티스토리를 잘 쓸 줄 몰라서...

만약 정말 공부하실 생각이라면 한 번 손으로 직접 그리면서 해보세요.

 

코드로 작성해보겠습니다!

 

n = int(input())
S = list(map(int, input().split()))
x = int(input())


def binary_search(low, high):
    # 이진 검색 함수
    if low > high:
        # low > high이면 분할할 수 없는 상태이므로 해당 값이 리스트 안에 없음
        # low == high인 상태는 배열에 원소가 하나 있으므로 이것은 아직 해당 값이 리스트 안에 없다는 뜻이 아님
        return -1
    else:
        mid = (low + high) // 2     # 리스트의 중간 위치
        if S[mid] == x:
            return mid
        elif S[mid] > x:
            return binary_search(low, mid-1)        # 왼쪽 subarray 탐색
        else:
            return binary_search(mid+1, high)       # 오른쪽 subarray 탐색


print(binary_search(0, n-1))

 

간단하죠? 

 

이때, 함수의 인자는 값이 변하는 값만 넘겨주면 됩니다.

n, S, x는 global variable로 해주세요.

---

2. 시간 복잡도 분석

 

입력 값 x에 따라 시간 복잡도가 달라지므로 every-case time complexity는 맞지 않으므로, worst-case를 파악하겠습니다.

이때, n은 2의 거듭제곱 수라고 가정하겠습니다.

 

basic operation은 비교 연산으로 가정하겠습니다. 이때, 비교 연산은 한 번만 한다고 가정하겠습니다.

찾으려는 수 x는 S의 어떤 값보다도 크다고 가정하겠습니다.

 

그러면 Worst-case는 \(W(n)\,=\,W(\frac{n}{2})+1\) 이 됩니다.

 

\(W(\frac{n}{2})\)는 분할한 subarray의 시간 복잡도이고

+1은 분할하기 위해서 한 번 비교하는 복잡도입니다.

 

이를 점화식으로 풀어내면 \(W(n)\,=\,lg(n)+1\)이 되겠네요.

 

점화식은 마스터 이론에서 설명드리겠습니다.

지금은 한 번 재귀할 때마다 반씩 줄어드므로 \(lg(n)\)라고만 아셔도 무방합니다.

 

즉 이 알고리즘은 \(\Theta(lg(n))\)에 속합니다.

 

참 빠른 알고리즘이죠?? 하지만 이건 정렬된 배열에서만 사용 가능하다는 점 항상 인지하고 계셔야합니다.

 

감사합니다.

 

지적 환영합니다.