Binary Search?
Binary Search는 오름차순 정렬된 자료에서 특정 데이터를 찾는 알고리즘이다.
Binary Search의 시간 복잡도는 O(logN)이다.
Linear Search?
Linear Search는 정렬되지 않은 자료에서도 특정 데이터를 찾을 수 있는 알고리즘이다.
Linear Search의 시간 복잡도는 O(N)이다.
Comparison
Binary Search는 특정 데이터를 기준으로 탐색 범위를 반씩 줄여간다.
Linear Search는 특정 데이터가 나타날 때까지 탐색을 순차적으로 이어간다.
Binary Search의 데이터 탐색 속도가 Linear Search보다 빠르다. (단, 오름차순 정렬된 자료여야 한다.)
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# array는 **오름차순 정렬**된 리스트여야 한다.
def binary_search(array, target):
low, high = 0, len(array)-1
while low <= high:
mid = (low+high)//2
# 목표값을 찾은 경우
if array[mid] == target:
# 참을 반환한다.
return True
# 현재값 < 목표값인 경우
elif array[mid] < target:
# low를 업데이트한다.
low = mid+1
# 현재값 > 목표값인 경우
elif array[mid] > target:
# high를 업데이트한다.
high = mid-1
# 목표값을 찾지 못한 경우
# 거짓을 반환한다.
return False