가장 첫번째로 배열의 중간 값을 기준으로 찾고자 하는 값 x와 비교한다.
만약 x가 중간 값보다 크면 중간 값을 기준으로 우측을 탐색하고,
x가 중간 값보다 작으면 좌측을 탐색한다.
새로 갱신 된 탐색 영역에서 같은 방법으로 새로운 중간 값과 비교해 x를 찾을 때까지 이를 반복한다.
예를 들어 [15, 17, 22, 29, 35, 47, 84] 이라는 배열 arr이 있다고 하자.
찾고자 하는 값 x는 35이다.
✔ step1
tmp(중간 값) = 29, x = 35
tmp < 35 이므로 tmp의 우측 탐색
✔ step2
arr = [35, 47, 84]
tmp = 47, x = 35
x < tmp 이므로 tmp의 좌측 탐색
✔ step3
arr = [35]
배열에 하나 남은 값과 x가 일치하므로 성공
배열의 길이가 0이 될 때까지 x를 찾지 못하면 실패하고 종료된다.
def binary_search(arr, x):
l, r, = 0, len(arr)-1
#l이 r보다 작거나 같을 동안
while l <= r:
m = (r + l) // 2
#중간값이 타겟값과 같을 경우 위치 리턴
if arr[m] == x:
return m
#중간값보다 타겟값이 작을 경우 중간값의 왼쪽 영역 탐색
elif x < arr[m]:
r = m - 1
#중간값보다 타겟값이 크거나 같을 경우 중간값의 오른쪽 영역 탐색
else:
l = m + 1
return -1
if __name__ == '__main__' :
arr = list(map(int, input().split()))
x = int(input())
print(binary_search(arr, x))
예를 들어
[12, 23, 34, 45, 56, 67, 78, 89]인 배열에서 12를 찾으려면
배열의 길이가 N일 때
원소의 개수가 8개 -> 4개 -> 2개 ->1개 로 줄어들며 탐색이 3번 진행된 것을 알 수 있다.
따라서 시간 복잡도를 k라 하고, 배열의 길이를 N이라 하면
2^K = N 이다.
K = log2N
-> logN
따라서 이진 탐색의 시간 복잡도는 O(logN)이다.