Programming/알고리즘
이분 탐색 (Binary Search)
weekyear
2021. 6. 10. 11:47
목표
- Binary Search에 대해 설명할 수 있다.
- Binary Search 과정에 대해 설명할 수 있다.
- Binary Search를 Python으로 구현할 수 있다.
- Binary Search의 특징을 이해하여 시간 복잡도와 공간 복잡도를 계산할 수 있다.
요약
- 탐색 범위를 두 부분으로 분할하면서 찾는 방식
- 처음부터 끝까지 순회하면서 탐색하는 것보다 훨씬 빠르다.
- 전체 탐색 : O(N), 이분 탐색 : O(logN)
과정
- 우선 주어진 배열을 정렬해야 한다.
- left, right로 mid 값을 구한다.
- mid와 내가 구하고자 하는 값과 비교하여 구할 값이 mid보다 높으면 left를 mid + 1로 설정한다.
- 구할 값이 mid보다 낮으면 right를 mid - 1로 설정한다.
- mid와 구할 값이 일치하면 종료한다.
Python 코드
def binary_search(lst, goal):
lst.sort()
left, right = 0, len(lst) - 1
while left < right:
mid = (left + right) // 2
if lst[mid] > goal:
right = mid - 1
elif lst[mid] < goal:
left = mid + 1
else:
break
print(binary_search([4, 3, 6, 2, 8, 1, 9, 5, 7], 6))시간 복잡도
- 시간 복잡도는 O(logN)이다.
공간 복잡도
기존에 주어진 배열에서 이루어지므로 공간 복잡도는 O(n)이다.
특징
장점
- 빠른 탐색
Reference
반응형