이진 탐색 알고리즘, 빅오표기법

정렬된 리스트에서 사용할 수 있는 알고리즘들

단순 탐색

• 리스트에 존재하는 요소들과 아이템을 하나씩 차례대로 비교하며 찾고자 하는 대상을 찾는 방식.
• 비교 아이템과 일치하는 요소를 찾을 때까지 반복.
• 한 번의 연산으로 하나의 요소가 비교 대상에서 제외됨

단순 탐색 알고리즘 (Python)

#list내에서 item을 탐색하여 index값을 반환해주는 함수
def simple_search(list, item):
	for i in range(0, len(list)):
		guess = list[i]
		if guess == item:
			return i
	return None

my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

print(simple_search(my_list, 6))	#5
print(simple_search(my_list, 1))	#0
print(simple_search(my_list, 10))	#9
print(simple_search(my_list, 11))	#None

 

이진 탐색

• 리스트 정렬 순서에서 중간에 위치하는 요소와 아이템을 비교하여 크고 작음을 판단한 후 중간 요소를 기준으로 범위를 줄여나가는 방식.
• 탐색 과정에서 중간 값이 변경되며 범위가 1개가 될 때까지 탐색을 반복.
• 한 번의 연산으로 절반(1/2)의 요소가 비교 대상에서 제외됨

이진 탐색 알고리즘 (Python)

# list내에서 item을 탐색하여 index값을 반환해주는 함수
def binary_search(list, item):
	low = 0                # minimum index
	high = len(list) - 1   # maximum index

	while low <= high:
		mid = (low + high) // 2  # middle index
		guess = list[mid]        # middle value

		if guess == item:
			return mid
		elif guess > item:
			high = mid-1
		else:
			low = mid+1
	return None

my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

print(binary_search(my_list, 6))	#5
print(binary_search(my_list, 1))	#0
print(binary_search(my_list, 10))	#9
print(binary_search(my_list, 11))	#None

 

 

반복문 종료 조건이 (low <= high)인 이유

이진 탐색은 탐색 과정에서 일치하는 아이템을 바로 찾지 못할 경우, 탐색 범위가 하나로 좁혀질 때까지 반복해야 한다.

탐색을 여러 번 반복하며 소거법 방식으로 결국 탐색범위가 하나로 좁혀졌는데도(low==high 상태, 이때는 mid값도 동일) if guess==item 조건이 부합하지 않아 return mid 하지 못하게 되면, elif guess>item 또는 else 조건을 타고 high값이 -1감소하거나 low값이 +1 증가해서 결과적으로 다음에는 low>high 상태가 된다. 이 때 반복문을 탈출하여 탐색을 끝냈으나 찾는 대상이 리스트에 존재하지 않는다고 return None을 해주게 되는 것.

 

 

ex) 리스트에 존재하지 않는 아이템으로 탐색 시도

빅오표기법

O(연산횟수)

• 알고리즘의 성능을 표시하는 기법
• 최악의 경우 알고리즘이 동작하기 위한 최대 연산 횟수
• 수행해야할 일이 많아질 때 알고리즘에 걸리는 시간이 어떤식으로 증가하는지
  ex) 리스트의 크기↑ = 타겟 아이템을 찾는데 필요한 연산 횟수↑

빅오 실행 시간에 따른 알고리즘

 

ex) 16개의 요소를 가진 리스트에서 특정 아이템을 탐색하는 데 필요한 최대 연산 횟수

이진 탐색 : O(log 16) = 4

단순 탐색 : O(16) = 16

 

연습문제 

1-1) 128개의 이름이 정렬되어 있는 리스트. 이진 탐색으로 이름을 찾을 때 필요한 최대의 추측 횟수는 얼마인가?

O(log 128) = 7

 

1-2) 만약 리스트의 크기가 두배가 된다면 최대 추측 횟수는 어떻게 되는가?

(= 256개의 이름이 정렬되어 있는 리스트)

O(log 256) = 8

 

다음 각각의 실행시간을 빅오표기법으로 나타내시오.

1-3) 어떤 사람의 이름을 알고있다. 전화번호부에서 이 사람의 전화번호를 찾고 싶다.

O(log n) 

 

1-4) 전화번호가 있다. 전화번호부에서 이 전화번호를 가진 사람의 이름을 찾고 싶다. 

O(n)

 

1-5) 전화번호부에 있는 모든 사람의 전화번호를 알고 싶다.

O(n)

 

1-6) 알파벳 A로 시작하는 사람들의 전화번호를 알고 싶다.

O(n/26)