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

Binary Search 이진 탐색

탐색 알고리즘 중 두번째, 이진 탐색이다. 순차 탐색은 그냥 말그대로 앞에서부터 쭈우우-욱 미련하게 찾는 것이었다면 binary search는 리스트를 반씩 쪼개면서 찾는 데이터가 없을 것이라고 판단한 반쪽 리스트는 과감히 버린다. 따라서 당연히 순차 탐색보다 계산량이 적다. 반복문을 쓰지는 않지만 재귀용법을 사용하여 그에 따른 시간 복잡도를 가진다.

 

알고리즘 구현

def binary_search(data_list, search):
    if len(data_list) == 1 and search == data_list[0]:
        return True
    if len(data_list) == 1 and search != data_list[0]:
        return False
    if len(data_list) == 0:
        return False

    medium = len(data_list) // 2
    if search == data_list[medium]:
        return True
    else:
        if search < data_list[medium]:
            return binary_search(data_list[:medium], search)
        else:
            return binary_search(data[medium+1:], search)

시간복잡도

• n개의 리스트를 쪼갤 수 없을 때까지 반으로 나눔
• 나누면서 비교(if)연산 수행 (반복문X)
• 리스트가 1이 되었을 때에도 비교연산을 한번 수행하므로 정확히 표기하면 $log2(n)+1$이 최종 시간복잡도 이지만, 빅오 표기법으로 쓰면 결국 $O(log(n))$

• 궁금한 점은 binary search에서 search하는 데이터 값이 있는지/없는지만 true/false로 return하지말고 찾고자하는 데이터의 index값을 return받을 수는 없을까..? 재귀함수에서 초기화하지 않고 변수의 값을 계속 유지하는 방법이 필요할 것 같은데...ㅠ_ㅠ
• 파이썬 내장함수 sort()함수는 어떤 정렬 알고리즘을 쓰는 걸까..? -> time sort라는 merge sort와 insertion sort를 섞어 놓은 알고리즘 방식을 사용한다고 한다... *[참고]