이진탐색 - Binary Search

 

• 정렬된 원소 리스트에서 시작한다.
• 리스트에 원하는 원소가 있으면 그 원소의 위치를 반환하고, 아니면 null 값을 반환한다.
• 매 번 남은 숫자 중의 가운데 숫자를 말하고, 대답에 따라 그 보다 큰 숫자 혹은 작은 숫자들을 한 번에 없앤다.
• n개의 원소를 가진 리스트에서 이진탐색을 이용하면 최대 $ log_2n$ 번 만에 대답을 찾을 수 있다.

 

low = 0
high = len(list) -1

mid = (low + high) // 2
guess = list[mid]

# 추측한 값이 작을 때 

if guess < item : 
	low = mid + 1

# 추측한 값이 너무 클 때

if guess > item : 
	high = mid - 1

 

알고리즘의 속도는 빅오 표기법에 의해서 O(연산횟수)로 표기할 수 있는데 여기서 중요한 점은 괄호 안의 숫자가 시간이 아니라, 연산횟수가 어떻게 증가하는지에 따라 달리진다는 점이다. (입력 데이터의 크기에 비례하여 달라짐.)

 

따라서 이를 통해 입력 데이터의 크기가 늘어날 때 알고리즘의 실행 속도가 얼마나 증가하는지를 알 수 있다.