이진 검색 알고리즘 w/파이썬

정렬된 데이터를 이진 검색을 활용하여 반띵.

 

내 신발 가격 10만원 업 다운?

업 -> 15만원 -> 다운-> 12만원 -> 업 -> 14만원!

 

평소에 이런식으로 물건 가격 맞추기 했던 기억을 되살려서 문제를 풀어보자.

 

로우 하이 인덱스값을 지정하고, 로우와 하이 인덱스의 중간지점에 평균 미드 인덱스를 지정한다.

그리고 그 미드인덱스 값이 찾는 값보다 큰지 작은지에 따라 로우/하이를 조정하여, 찾는 값이 나올때까지 while반복.

#검색알고리즘(search algorithm): 주어진 데이터에서 특정 데이터를 찾음
#정렬되어있는 데이터를 이진검색을 사용하여 반띵나눠서 검색
def main():

	#[1]input
	data = [1,3,5,7,9] #오름차순정렬로 가정 - 안되어있는 경우 정렬 필요
	n = len(data)
	search = 3 #검색할 데이터

	flag = False #플래그변수 : 찾으면 true 못찾으면 false
	index = -1 #인덱스변수 초기화

	#[2]process: 이진검색 알고리즘 : FULL-> INDEX SCAN
	low = 0 #min: 낮은 인덱스
	high = n-1 #max: 높은 인덱스

	while low <= high:
		mid = int((low + high) / 2) #중간 인덱스 = 로우 하이 평균, 정수형으로 처리해야
				
		if data[mid] > search: 
			high = mid - 1 #찾을 데이터가 작으면 하이 왼쪽으로 이동
		elif data[mid] < search:
			low = mid + 1 #찾을 데이터가 크면 로우 오른쪽으로 이동
		else:
			flag = True; index=mid; break;

	#[3]output
	if flag:
		print(f"{search}을(를) {index}에서 찾았습니다.")
	else:
		print("찾지 못했습니다")


main()

반응형

뭐를 좀 알아야 인강을 듣든 말든 코테를 준비를 하든말든 싶었는데,

주언어는 달라도 차근히 배우니까 뭐라도 좀 쌓이기 시작하는 느낌.

매일 꾸준히 공부하기.