순차 탐색
앞에서부터 하나씩 차례대로 탐색하는 방법
array = [3, 1, 7, 5, 9]
for i in range(len(array)):
if array[i] == 7:
print(i)
break
리스트를 차례대로 순회하므로 시간 복잡도는 O(N)이다.
이진 탐색
정렬된 리스트에 대하여 찾으려는 데이터와 중간 지점의 데이터를 비교해나가며 탐색하는 방법
- 순차 탐색과 달리 정렬이 되어 있어야 사용할 수 있다.
- 중간이 정확히 안 나누어질 때는 소수점 이하를 버린다.
시간 복잡도는 O(logN)이다.
구현
def binary_search(array, target, start, end):
while start <= end:
middle = (start + end) // 2
if target > array[middle]:
start = middle + 1
elif target < array[middle]:
end = middle - 1
else:
return middle
return None
array = [1, 3, 5, 7, 9]
target = 7
index = binary_search(array, target, 0, len(array) - 1)
print(index) if index != None else print("원소가 존재하지 않습니다.")
이진 탐색을 사용하는 경우
찾아야 할 자료가 여러 개인 경우
- 총 데이터 수가 N개, 찾아야 할 자료가 M개일 때 순차 탐색을 이용하면
O(M * N)만큼의 시간이 걸린다.
그러나 이진 탐색을 이용하면 탐색에O(MlogN)만큼의 시간이 걸리므로, 정렬에 너무 큰 시간을 소요하지 않는다면 M의 값이 커질수록 이진 탐색을 이용한 탐색이 더 효율적이게 된다. - 값의 범위가 크지 않은 경우에는 계수 정렬을 이용할 수도 있다.
- 또한 자료의 인덱스가 아니라 단순 자료의 유무 여부를 판단하는 문제라면 집합을 이용하는 것이 더 효율적일 수도 있다.
최적화 문제를 결정 문제로 바꾸는 파라매트릭 서치 문제
정답이 될 수 있는 수의 범위를 정하고 이 범위 내에서 이진 탐색을 수행한다.
- 1부터 100까지 라고 정하면 [1, 2, 3, ... , 99, 100] 이라는 가상의 배열이 있다고 가정
- target 값과 가까워지기 위해 중간값을 산정할수록 항상 최적의 값에 가까워진다는 점을 이용