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

1. 이진 탐색 알고리즘

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

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

 

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

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

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

 

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

 

2. 코딩

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

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

      

      

      

    
    

      <python />
    
# -*- 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() 메소드를 참고하면 된다.

 

2.1. 결론

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

 

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

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

 

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

3. Reference

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