이분 탐색 알고리즘(Binary Search Algorithm)

이분 탐색

이분 탐색이란 정렬되어 있는 배열(중요*)에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하지 않고 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법이다. 만약 순차적으로 확인한다면 이건 선형 탐색이라고 하는 탐색법이 된다. 선형 탐색은 $O(n)$, 이분 탐색은 $O(logn)$으로 배열의 크기가 커질수록 이분 탐색의 선형 탐색 대비 효율성이 더욱 더 증가한다.

예제풀며 배워보기

간단한 수로 이분 탐색을 배워보자.

| 4 | 1 | 5 | 2 | 3 | |—|—|—|—|—|

위와 같은 배열이 있다. 위 배열을 정렬시킨다.

1	2	3	4	5	2
st		md		en	target

정렬시킨 처음, 중간, 끝을 각각의 변수(st, md, en)에 저장한다. 찾는 수 2는 target 변수에 저장한다.

그리고 md와 target을 계속 비교하며 절반으로 줄여나가면 된다. md(3)보다 target(2)가 작으므로 정렬된 배열에서 찾는 수가 있는 곳은 왼쪽의 배열, 즉

1	2	3	4	5
★	★	★

이 곳에 있게 된다. 새롭게 st, md, en 을 정해준다.

1	2	3	4	5
st	md	en

다시 비교해보면 md == target으로 같은 수가 나온다. 반복문을 나오며 종료한다.

만약에 target이 배열 안에 없다면, st, md, en이 전부 같은 곳에 있게 된다.

1	2	3	4	5
	st md en

그러므로 배열이 없을 때 $st>=en$일 때도 반복문을 나오며 종료한다.

arr = [4, 1, 5, 2, 3] # 입력된 배열
arr.sort() # 파이썬의 정렬 함수 sort()는 시간복잡도가 O(nlogn)이다.
target = 2 # 예제 타겟 설정

# 초기 st, en, md 지점 설정
st = 0 # 배열의 처음
en = len(arr) - 1 # 배열의 끝
md = int((st + en) / 2) # 배열의 중간

while True: # 다른 조건이 없으면 st<=en 으로 하면 됨
    if arr[md] == target:
        print(1)
        break
    elif arr[md] > target:
        en = md - 1
        md = int((st + en) / 2)
    elif arr[md] < target:
        st = md + 1
        md = int((st + en) / 2)

    if st >= en: # 종료 조건
        print(0)
        break