이진 탐색 (Binary Search) 알고리즘 with Python3

이진 탐색 알고리즘

이진 탐색(Binary Search) 알고리즘은 순차 탐색 알고리즘보다 더 빠르게 탐색할 수 있다.

빠르게 탐색할 수 있는 이유는 둘로 분할(이분)하여 탐색하기 때문이다.

 

예를들어, 1000페이지까지 있는 책이 있을때 630페이지를 찾으려고 한다.

우리는 대충 책을 펼쳐서 페이지를 확인한다. 그때 500페이지라면 630 페이지는 500페이지보다 뒤에 있으므로

앞 페이지를 살펴볼 필요가 없어진다.

 

하지만, 이진 탐색을 하려면 위 예제와 같이 탐색할 데이터 그룹이 정렬이 되어 있어야한다는 조건이 있다.

 

코딩

반으로 나누어서 중간 값과 목표값(target)을 비교한다.

• 같다: 인덱스를 반환한다.
• 목표값이 중간값보다 작다: 중간값의 인덱스보다 작은 왼쪽에서 다시 찾는다. (오른쪽은 버려도된다)
• 목표값이 중간값보다 크다: 중간값의 인덱스보다 큰 오른쪽에서 다시 찾는다. (왼쪽은 버려도된다)

# -*- coding: utf-8 -*-

import unittest


def binary_search(data, target):
    """data 에서 target 의 인덱스를 찾아 반환한다.

    :param data: 데이터 리스트
    :param target: 찾고 있는 수
    :return: target 의 인덱스
    """
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (end + start) // 2

        if data[mid] == target:
            return mid
        elif data[mid] < target:
            start = mid + 1
        elif data[mid] > target:
            end = mid - 1

    return -1


class Exam13(unittest.TestCase):

    def test_binary_search(self):
        data = [1, 4, 9, 16, 25, 36, 49, 64, 81]
        self.assertEqual(0, binary_search(data, 1))
        self.assertEqual(1, binary_search(data, 4))
        self.assertEqual(2, binary_search(data, 9))
        self.assertEqual(3, binary_search(data, 16))
        self.assertEqual(4, binary_search(data, 25))
        self.assertEqual(5, binary_search(data, 36))
        self.assertEqual(6, binary_search(data, 49))
        self.assertEqual(7, binary_search(data, 64))
        self.assertEqual(8, binary_search(data, 81))
        self.assertEqual(-1, binary_search(data, 0))
        self.assertEqual(-1, binary_search(data, 999))


if __name__ == "__main__":
    unittest.main()

위 코드는 unittest 기반으로 작성되었다. 알고리즘은 binary_search() 메소드를 참고하면 된다.

 

결론

이분 탐색(Binary Search)은 순차 탐색(O(N))보다 효율적인 알고리즘으로, 시간복잡도는 O(logN)을 가진다.

 

예를들어봐도 상당히 차이가 크다. 5천만명을 찾는다고 할때,

순차 탐색은 최악의 경우 50,000,000번을 비교하지만, 이분 탐색은 log50000000 = 25.575 로 약 2백만배 차이가 난다.

 

물론 이분 탐색을 하려면 데이터가 이미 순차적으로 정렬이되어 있어야한다는 단점이 있다. 하지만, 정렬을 하고 이분 탐색을 하는 것이 더 효율적일 수 있다.

Reference

• https://thebook.io/006935/part03/ch12/02-02/