[알고리즘] 이진탐색에서 한 나의 실수

1. left와 right 초기화

단순히 리스트의 길이를 right로 초기화 하면 인덱스의 길이와 맞지 않아 런타임 에러(IndexError)가 발생한다.

lst = [1,2,3,4] # 인덱스의 최대값은 3, 길이는 4

left, right = 0, len(lst) -1 # 여기서 1을 빼주지 않으면 lst[4]를 할 수 있어 인덱스 에러 발생

 

2. while left <= right

나의 경우에는 등호를 빼먹었었다. 등호를 넣어야 아래 형태처럼 left right 갱신 시에 비슷한 형태를 짤 수 있으니 기억해두자

        if ns[mid] > target:
            right = mid - 1
        elif ns[mid] < target:
            left = mid + 1