이진탐색

Last updated - 2024년 10월 29일 Edit Source

코드트리(Codetree)의 Novice High - 자료구조 알고리즘을 정리한 내용입니다.

그림은 해당 내용을 참고하여 그렸습니다.

# Binary Search

찾아야 하는 수의 범위 중 가운데 값과 찾고자 하는 값을 비교하여 대소 관계에 따라 특정 구간으로 이동 반복
left는 mid + 1이고, right는 mid - 1인 이유
- mid는 target을 포함할 숫자 범위에서 명확히 제외해야하니까
시간 복잡도
- 정렬된 상태 : $O(log N)$
- 정렬되지 않은 상태 : $O(N log N + log N)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function binary_search(arr, target)
	set left = 0
	set right = arr.size - 1
	while (left <= right)
		set mid = (left + right) / 2
		if arr[mid] == target
			return mid

		if arr[mid] > target
			right = mid - 1
		else
			left = mid + 1

	return -1

Comment