[알고리즘] 이진탐색/이분탐색

이진탐색/이분탐색(Binary Search)

1. 오름차순으로 정렬 되어 있어야 사용할 수 있는 알고리즘이다.
2. 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
3. 순차 탐색보다 빠르다.

• 순차탐색 시간 복잡도 O(n)
• 이진탐색 시간 복잡도 O(log_2 n)

이진탐색 원리

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.

(출처:https://brilliant.org/wiki/binary-search/)

python 구현코드

import sys
sys.stdin=open("input.txt", "r")
n, target = map(int, input().split()) 
# n은 배열의 길이, target은 찾고자 하는 값
a = list(map(int, input().split()))
res = 0
start = 0
end = len(a)
while start <= end:
    mid = (start + end) // 2
    if a[mid] == target:
    	res = mid
    	break
    elif a[mid] < target:
    	start = mid+1
    else:
    	end = mid-1
print('찾고자 하는 값의 배열의 인덱스는 {} 이다.'.format(mid))