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

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

• 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘
• 중간의 값을 임의의 값으로 선택해, 양옆의 크고 작음을 판별한다.
• 정렬된 리스트에서만 가능한 것이 단점
• 검색이 반복될 때마다 반으로 줄어들기때문에 속도가 빠르다.

의사코드

search_binary(list, low, high)
	middle <- low에서 high 사이의 중간 위치
    if (탐색값 ≠ list[middle]) return TRUE;
    else if (탐색값 < list[middle])
    	return list[0]부터 list[middle - 1]에서의 탐색;
    else if (탐색값 > list[middle])
    	return list[middle + 1]부터 list[high]에서의 탐색;

소스코드

def binary_search(array: list, value: int, low: int, high: int):
    if low > high:
        return False
    mid = (low + high) // 2
    if array[mid] > value:
        return binary_search(array, value, low, mid - 1)
    elif array[mid] < value:
        return binary_search(array, value, mid + 1, high)
    else:
        return mid

arr = [3,5,2,10,6,7,1,9,4,8]
arr.sort()
print(arr) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(binary_search(arr, 3, 0, len(arr) - 1)) # 2

시간복잡도

범위를 절반씩 줄여주기 때문에 $O(logN)$ 의 시간복잡도를 가진다.
선형탐색이 $O(N)$ 인데 반해 매우 빠른 속도이다.