[알고리즘 기본] 이분 탐색 알고리즘
이분 탐색 (Binary Search)
- 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.
- 이분 탐색(Binary Search)의 이분은 '둘로 나눈다'는 뜻이다. 탐색할 자료를 둘로 나누어 찾는 값이 있을 법한 곳만 탐색한다.
- 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있다.
- 하지만 검색이 반복될 때마다 목표값을 찾을 확률이 두 배가 되므로 속도가 빠르다는 장점이 있다.
전개
- 배열을 정렬한다.
- 중간 위치를 찾는다.
- 찾은 값과 중간 위치 값을 비교한다.
- 같다면 원하는 값을 찾았으므로 위치 번호를 결괏값으로 돌려준다.
- 찾는 값이 중간 위치 값보다 크다면 중간 위치의 오른쪽 배열을 대상으로 다시 탐색한다.(1번 과정부터 반복)
- 찾는 값이 중간 위치 값보다 작다면 중간 위치의 왼쪽 배열을 대상으로 다시 탐색한다.(1번 과정부터 반복)
시간 복잡도
- 이분 탐색은 값을 비교할 때마다 찾는 값이 있을 범위를 절반씩 좁혀나간다.
- 절반씩 좁혀나가는 과정이 있으므로 시간 복잡도는 O()이다.
구현 코드
def binary_search(numbers, target):
"""
이분 탐색 알고리즘으로 특정 값을 찾는다.
값이 있으면 값의 인덱스를 반환하고,
값이 없으면 -1를 반환한다.
"""
left = 0
right = len(numbers) - 1
while left <= right:
mid = (left + right) // 2
if target == numbers[mid]:
return mid
elif target > numbers[mid]:
left = mid + 1
else:
right = mid - 1
return -1
if __name__ == '__main__':
numbers = [6, 5, 6, 4, 3, 2, 1]
target = 3
numbers.sort()
target_idx = binary_search(numbers, target)
print(numbers)
print(target_idx)
'''
출력 결과
[1, 2, 3, 4, 5, 6, 6]
2
'''
Ref
Author And Source
이 문제에 관하여([알고리즘 기본] 이분 탐색 알고리즘), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@bky373/알고리즘-기본-이분-탐색-알고리즘
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
Author And Source
이 문제에 관하여([알고리즘 기본] 이분 탐색 알고리즘), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@bky373/알고리즘-기본-이분-탐색-알고리즘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)