알고리즘) 이진탐색

이진탐색은 쉽게 생각해서 up-down 게임이랑 똑같습니다. 

저희가 친구들 나이 맞추기 할때, up-down 많이 하잖아요? 어떤 수를 부르고 상대가 up하면 더 큰 수를 부르고, 거기서 down이라고 얘기하면 처음 불렀던 수와 두번째로 불렀던 수 사이를 얘기하는 것처럼요

이진탐색도 그렇습니다. 어떤 정렬된 숫자열이 있을때, 숫자열의 가운데에 위치한 요소와 탐색 타겟을 비교해서 더 크면 숫자열을 반으로 나눈 뒤, 가운데 수보다 큰 영역을 잡아서 또 그 가운데 수를 비교합니다. 만약 작다면 작은 영역을 잡아서요. 이렇게 계속 반복해 가는 것입니다. 

반복한다는 점에서 재귀 용법을 사용하지요

코드는 다음과 같습니다. 

def binary_search(data_array, target):
	if len(data_array) == 1 and target == data_array[0]:
    	return True
    elif len(data_array) == 1 and target != data_array[0]:
    	return False
    elif len(data_array) == 0 : #방어코드
    	return False
    
    mid = int(len(data_array)/2)
    if target == data_array[mid]:
    	return True
    elif target > dat_array[mid] :
    	return binary_search(data_array[mid+1:],target)
    elif target < data_array[mid]:
    	return binary_search(data_array[:mid], target)

이진 탐색 또한 계속 반으로 나누는 것이기 때문에 시간 복잡도가 O(logN)입니다.