이진 탐색

Binary_Search

by JichangJang, https://github.com/jangjichang

개념

정렬된 데이터들의 배열에서 특정한 값의 위치를 찾는 알고리즘입니다. 절차는 다음과 같습니다.

 

1. 배열 중간에 있는 요소를 대상 값과 비교합니다.
2. 대상 값이 요소와 일치하면 요소의 위치(인덱스)를 반환합니다.
3. 대상 값이 요소보다 작으면 배열의 아래쪽 절반에서 1번 단계를 시작합니다.
4. 대상 값이 요소보다 크면 배열의 위쪽 절반에서 1번 단계를 시작합니다.
5. 더 이상 비교할 요소가 없으면 대상 값은 배열에 존재하지 않습니다.

 

연산

정렬된 배열에서 대상 값을 찾는 연산이 있습니다. 시간 복잡도는 아래와 같습니다.

 

	Best	Worst	Avg
시간 복잡도	O(1)	O(logn)	O(logn)

 

최선의 경우 배열 중간에 있는 요소가 대상 값과 일치하는 경우 한 번의 비교로 연산이 종료됩니다. 따라서 시간 복잡도는 O(1)입니다.

 

최악의 경우를 생각해보겠습니다. 처음에는 원소 n개가 들어 있는 배열에서 시작합니다. 한 단계가 지나면 탐색해야 할 원소의 개수가 n/2로 줄어들고, 한 단계가 더 지나면 n/4개로 줄어듭니다. 그러다가 원소를 찾았거나 탐색해야 할 원소가 하나만 남으면 탐색을 중지합니다. 총 수행 시간은 n을 절반씩 나누는 과정에서 몇 단계 만에 1이 되는지에 따라 결정됩니다.

 

n = 16

n = 8

n = 4

n = 2

n = 1

 

16에서 1로 감소하는 순서를 뒤집어서 1에서 16으로 증가하는 순서로 생각해 보겠습니다.. 숫자 1에 2를 몇번 곱해야 n이 될까요?

즉 2^k = n을 만족하는 k는 무엇인가요? 이때 사용되는 것이 바로 로그(log)입니다.

2⁴ = 16 -> log₂16 = 4

log₂N = k -> 2^k = n

따라서 k는 log₂N, 시간 복잡도는 O(log₂N)입니다.

 

구현

sorted_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]


def binary_search(array, n):
    low = 0
    high = len(array)-1

    while low <= high:
        pivot = (low+high) // 2

        if array[pivot] == n:
            return pivot
        elif array[pivot] < n:
            low = pivot + 1
        else:
            high = pivot - 1
    return -1


if __name__ == "__main__":
    for i in range(13):
        print(binary_search(sorted_list, i))

관련 문제

• https://leetcode.com/problems/intersection-of-two-arrays-ii/
• https://leetcode.com/problems/find-the-duplicate-number/

참고

• 코딩 인터뷰 완전 분석 (big-O)