이분 탐색으로 리트스의 특정 값 위치 찾기 알고리즘
# 리스트에서 이분 탐색으로 특정 숫자 위치 찾기
# 입력: 리스트 a, 찾는 값 x
# 출력: 찾으면 그 값으 위치, 찾지 못하면 -1
def binary_search(a, x):
# 탐색할 범위를 저장하는 변수 start, end
# 리스트 전체를 범위로 탐색 시작(0 ~ len(a)-1)
start = 0
end = len(a) - 1
while start <= end: # 탐색할 범위가 남아 있는 동안 반복
mid = (start + end) // 2 # 탐색 범위의 중간 위치
if x == a[mid]: # 발견
return mid
elif x > a[mid]: # 찾는 값이 더 크면 오른쪽으로 범위를 좁혀 계속 탐색
start = mid + 1
else:
end = mid - 1 # 찾는 값이 더 작으면 왼쪽으로 범위를 좁혀 계속 탐색
return -1 # 찾지 못했을때
l = [1, 4, 9, 16, 25, 36, 49, 64, 81]
print(binary_search(l, 16))
print(binary_search(l, 81))
실행 결과
'개발 공부한 내용 정리 > Algorithm' 카테고리의 다른 글
Algorithm- 딕셔너리를 이용한 동명이인 찾기 알고리즘 (0) | 2020.08.20 |
---|---|
Algorithm- 큐와 스택을 활용한 회문(똑바로 읽어도 거꾸로 읽어도 같은 단어나 문장) 찾기 (0) | 2020.08.19 |
Algorithm- 퀵 정렬 알고리즘 (0) | 2020.08.17 |
Algorithm- 병합 정렬 (0) | 2020.08.16 |
Algorithm- 삽입 정렬 알고리즘 (0) | 2020.08.15 |