이분검색

lt=0
rt=n-1
while lt<=rt:
    mid=(lt+rt)//2
    if a[mid]==m:
        print(mid+1)
        break
    elif a[mid]>m:
        rt=mid-1
    else:
        lt=mid+1

 

 

a라는 정렬된 숫자 리스트가 주어졌을 때

lt는 왼쪽 인덱스로 0, rt는 오른쪽 인덱스로 (리스트의 크기-1)로 시작한다. 또한 mid는 lt와 rt를 더한 값을 2로 나누었을 때 몫을 말한다.

 

while문을 lt가 rt보다 작거나 같다면 계속 진행하는데 (lt<=rt) 이는 현재 탐색 범위가 남아 있을 때까지 계속해서 이분 탐색을 반복한다는 의미이다. 즉, 왼쪽 인덱스가 오른쪽 인덱스보다 크거나 같으면 여전히 탐색해야 할 구간이 있다는 뜻이다.

 

반면 lt가 rt보다 커지면 더 이상 탐색할 구간이 없다는 의미이기 때문에 반복문을 종료해야 한다. 이 조건을 설정하지 않으면 탐색 범위가 끝난 뒤에도 불필요하게 반복문이 실행될 수 있다.

 

아래에서 예시를 들어보았다.

'''
a=[1, 3, 5, 7, 9, 10, 13, 14, 15]
에서 m=5을 찾고자 할 때
'''

# 1)
lt=0
rt=8
mid=(0+8)//2=4
a[mid]>m -> 9>5 -> rt=mid-1 -> rt=3

# 2)
lt=0
rt=3
mid=(0+3)//2=1
a[mid]<m -> 3<5 -> lt=mid+1 => lt=2

# 3)
lt=2
rt=3
mid=(2+3)//2=2
a[mid]==m -> 2==2 -> break

# while문 종료
print(mid+1) -> 3 -> 숫자 5는 3번째에 위치