이진검색(binary search) 파이썬 반복문으로 구현

#1 서론

이진검색(binary search)는 시간복잡도가 O(log n)으로 빠르다.

다만 구현이 조금 까다롭다.

이번 글에선 구현을 완전 익혀보려 한다.

 

#2 본론

찾고자하는 값을 target변수에 저장해 주었고, target이 들어있는 배열 A를 저장 해 주었다.

이진검색을 사용하려면 배열이 오름차순으로 정렬되어있어야 한다.

 

구현:

A = [1, 2, 3, 4, 5, 6]

target = 5

start = 0
end = len(A)-1

while start <= end:
	mid = (start + end) // 2
	
	if A[mid] == target: #타겟을 찾은 경우
		print(mid) #타겟의 인덱스 반환
		break

	elif target < A[mid]:
		end = mid -1

	elif target > A[mid]:
		start = mid +1