알고리즘
[알고리즘] 이분 탐색
훈꽁
2021. 6. 9. 22:15
이분탐색이란 무엇일까?
- 정렬된 자료를 반으로 나누어 탐색하는 방법
- 시간 복잡도 :
O(log N)
코드 분석
def binary_search(left, right, target):
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
right = mid - 1
else:
left = mid + 1
return None
- 움직여야 하는 값, 즉, 이 값을 움직여야 겠다. 를 정렬
- 자료의 중간 값이 찾고자 하는 값인지를 검사
- 아니면 대소관계를 비교하여 left와 right를 이동
- 맞으면 함수를 끝낸다.
STEP 00 (기본)
STEP 01 (중간 값 > Target)
STEP 02 (중간 값 < Target)
STEP 03 (중간 값 == Target)
- 종료
백준 참고 문제
https://www.acmicpc.net/problemset?sort=ac_desc&algo=12
문제 - 1 페이지
www.acmicpc.net
❤ 본 포스팅에서 지적과 좋아요는 감사하게 받겠습니다.