이진 탐색 Binary Search 경계 설정을 어떻게 해야 하는가

이진 탐색은 쉬운듯 하면서도 어려운 알고리즘이다.

경계를 잘못 설정하면 while 문을 빠져나오지 못 하게 된다. 그렇다고 여러 테스트 케이스를 매번 고려하면서 짜기에는 시간이 너무 오래 걸린다. 어느 조건에 =을 넣어줘야 하며 left, right 갱신 시 mid로 할지 mid -1 혹은 mid + 1로 할지 고민하는 건 꽤나 골치 아픈 일이다. 

그래서 나름의 템플릿이 있으면 빠르게 이진 탐색 코드를 짤 수 있겠다는 생각이 들어서 정리하는 중이다.

 

 

가장 기본 형태

left, right = 0, len(arr) - 1
while left < right:
    mid = left + (right - left) // 2
    if arr[mid] < target:
        left = mid + 1
    else:
        right = mid
        
return arr[left]

left = mid 는 사용하면 안 된다.

조건에 따라 될 수도 있겠지만 위 조건에서 left = mid를 사용하면 left, right 사이에 두 원소만 남았을 때 left가 움직이지 못 하므로 무한루프에 빠진다.

mid 계산 시 정수로 내림하기 때문에 주의해야 할 점이다.

 

left = mid는 안 되는데 right = mid는 왜 되는가?

mid 계산 특성 (정수 내림) 때문이다.

두 원소만 남은 경우 mid는 left랑 같고 조건식을 만족하면 left가 right로 이동하고 조건식을 만족하지 않으면 right가 mid(이 경우에는 left랑 같음)로 이동하므로 left == right여서 반복문을 빠져나온다.

 

 

while 조건에 equal 포함 형태

left, right = 0, len(arr) - 1
while left <= right:
    mid = left + (right - left) // 2
    if arr[mid] < target:
        left = mid + 1
    else:
        right = mid - 1
        
return arr[left]

 

right = mid를 사용할 경우 left == right, arr[mid] == target 일 때 반복문을 못 빠져나오는 경우가 생긴다. 그래서 while 조건에서 등호가 포함되어 있을 경우 right = mid - 1을 사용한다.

 

right = mid -1 을 사용하면 [left, right] 사이에 답이 없는 경우가 생기는데 괜찮나?

간단하게 arr = [1, 3, 3, 5], target = 3 을 살펴보자.

첫 번째 루프에서 mid = index 1이 되고 arr[mid] == target이기 때문에 right = index 0이 된다.

left = right = index 0인 상태, 즉 arr[left : right+1] = [1]

target 값인 3이 포함되어 있지 않다.

하지만 걱정할 필요가 없다. right는 최대로 왼쪽으로 가봤자 가장 왼쪽에 있는 (target 이상의 값) 인덱스 - 1 이다.

이 명제가 중요하다. 그리고 while의 등호 때문에 left == right여도 한번 더 left 또는 right의 움직임이 있다는 점 또한 중요하다.

[1] 상태에서 target보다 작기 때문에 결국 left가 1 증가해서 값이 3인 원소를 가리키며 반복문이 끝난다.

 

 

target이 존재하는지 판단해야 한다면

right를 배열의 가장 마지막 원소의 인덱스 + 1로 설정해주면 좋다