[알고리즘] 이진 탐색(Binary Search)

이진 탐색 (Binary Search)

• 탐색: 순차 탐색, 이진 탐색, 해쉬
• 리스트를 두 개로 나뉜뒤, 가운데 중간값과 검색 대상값을 비교한다.
• 가운데 중간값 > 검색 대상값, 앞 부분 리스트에서 반복해서 검색한다.
• 가운데 중간값 < 검색 대상값, 뒷 부분 리스트에서 반복해서 검색한다.
• 시간 복잡도 : O(logn)

이진 탐색 구현하기

def binary_search(data, 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
    
    medium = len(data) // 2
    if search == data[medium]:
        return True
    else:
        # 검색한 값이 중간값보다 큰 경우, 뒷 부분 리스트를 받는다.
        if search > data[medium]:
            return binary_search(data[medium+1:], search)
        
        # 검색한 값이 중간값보다 작은 경우, 앞 부분 리스트를 받는다.
        else:
            return binary_search(data[:medium], search)

import random
data_list = random.sample(range(100), 10)
data_list

Out[2]:

[93, 57, 4, 35, 87, 20, 60, 0, 1, 95]

data_list.sort()

data_list

Out[4]:

[0, 1, 4, 20, 35, 57, 60, 87, 93, 95]

binary_search(data_list, 4)

Out[5]:

True

 

GitHub - DAWUNHAN/Algorithms-and-DataStructure: Algorithms and DataStructure with Python