정렬되어 있는 배열에서 데이터를 찾으려 시도할 때,
순차 탐색처럼 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 찾는 것이 아니라
탐색 범위를 절반씩 줄여가며 찾아가는 Search 방법입니다.

시간복잡도

처음부터 끝까지 우너하는 값을 찾을 때까지 탐색을 계속하는 순차 탐색은 Worst Case일 때 O(n)이라는 Time complexity를 보여줍니다.

10만개의 데이터가 있다면 무려 10만번을 탐색해야합니다.
그러나 Binary Search는 탐색 대상을 절반씩 계속해서 줄여나가기 때문에, Worst Case일때도 탐색의 횟수가 logn이 되므로 10만개의 데이터가 있다고해도 약 16번정도로 탐색을 끝낼 수 있습니다.

시간복잡도는 O(log n) 입니다.

구현

def binary_search(target, data):
	data.sort()
    start = 0 
    end = len(data) - 1
    
    while start <= end:
    	mid (start + end) // 2
        
        if data[mid] == target:
        	return mid
        elif data[mid] < target:
        	start = mid + 1
        else:
        	end = mid - 1
        
   return None

재귀적으로도 구현을 할 수 있습니다.

def binary_search_recursion(target, start, end, data):
	if start > end:
    	return None
    
    mid = (start + end) // 2
    
    if data[mid] == target:
    	return mid
    elif data[mid] > target:
    	end = mid - 1
    else: 
    	start = mid + 1
        
    return binary_search_recursion(target, start, end, data)