똑똑한 코드 작성을 위한 실전 알고리즘

67

2

장

알고리즘 분석

그림

2-6

정렬된 배열에 포함되지 않은

17

탐색하기

세 번째

while

루프에서

A

[

mid

]

가 목푯값

17

보다 더 작은 값인

15

가 된다. 다시 한번

elif

라인을 수행해

lo

가

hi

보다 더 높은 값으로 설정되어 [그림

2

-

6

]의 마지막 그림과 같이 ‘교차’

가 일어난다.

2.9

이진 배열 탐색의 또 다른 기능

A

에서

target

의 포함 유무가 아니라 정확한 위치를 알고 싶다면 어떻게 해야 할까? 현재 이진

배열 탐색은

True

나

False

를 반환한다. [코드

2

-

4

]와 같이 코드를 수정하면

target

을 찾으

면 위치 인덱스인

mid

를 반환한다.

첫 번째 탐색

두 번째 탐색

세 번째 탐색

네 번째 탐색

68

똑똑한 코드 작성을 위한 실전 알고리즘

코드

2-4

배열

A

내

target

의 위치 반환하기

def binary_array_search(A, target):

lo = 0

hi = len(A) - 1

while lo <= hi:

mid = (lo + hi) // 2

if target < A[mid]:

hi = mid-1

elif target > A[mid]: