[Algorithm] Binary Search 101

References

이진 탐색(Binary Search)

어떠한 group에서 target을 찾으려면, 최악의 경우에는 모든 원소를 다 확인함으로써 O(n)에 작업을 수행하게 된다.

하지만 원소들이 정렬되어 있다면, search time을 O(logn)으로 줄일 수 있다.

탐색 방법	복잡도
binary search	$O(\log n)$
sequential search	$O(n)$

이진 탐색 문제 풀이 시 고려해야 하는 세 가지

루프 탈출 조건
경계 변수 lo와 hi의 초기값
경계 축소 방법

풀이 원칙

lo & hi를 초기화할 때는 가능한 모든 정답 범위를 포함하도록 한다.

일반적으로 배열의 원소에서 target을 찾는 경우, lo와 hi는 배열의 인덱스의 범위와 같다.
```
lo = 0
hi = len(nums) - 1
```
하지만 배열에 target 원소를 끼워넣는 등 특수한 경우에는 다음과 같이 hi를 하나 더 고려해야 한다.

ex. 69. Sqrt(x) / 35. Search Insert Position
```
lo = 0
hi = len(nums)
```
mid 계산 시 오버플로우와 lower/upper mid 에 주의한다.
1. 오버플로우가 일어나지 않도록 한다.
  
  int overflow가 없는 Python은 상관 없다고 알고있으나, lower/upper mid를 이용하려면 두 번째 방법이 쉬워보인다.
```
# worst
mid = (lo + hi) // 2

# much better, but still possible
mid = lo + (hi - lo) // 2

# best
mid = (lo + hi) >> 1
```
2. lower/upper mid 중 적절한 것을 선택한다. 잘못 선택하면 무한 루프에 빠질 수 있다.
  
  → 5번에서 자세히 다룬다.
```
# lower(left) mid
mid = lo + (hi - lo) // 2

# upper(right) mid
mid = lo + (hi - lo + 1) // 2
```
경계를 축소해나갈 때, mid를 제외하는 로직을 사용한다.

단순한 논리를 위해 단일 쌍의 if ... else를 사용하며, 항상 mid를 제외하는 로직을 사용한다.

개인적인 견해로는, mid를 제외하는 로직과 포함하는 로직 중 더 직관적인 로직을 사용하는 편이 좋은 것 같다.
```
if target < nums[mid]:
    hi = mid - 1 # mid is excluded
else:
    lo = mid # mid is included
```
```
if target > nums[mid]:
    lo = mid + 1 # mid is excluded
else:
    hi = mid # mid is included
```
while 문의 조건은 항상 lo < hi 로 하는 것이 간단하다.

while lo < hi: 루프가 종료되는 유일한 조건은 lo == hi이며, lo와 hi가 같은 요소를 가리킬 것이라는 것을 알고 있으므로 lo < hi를 채택한다.

하지만 lo <= hi가 더 직관적인 경우가 있으므로, 때에 따라 적절하게 적용하자.

ex. 162. Find Peak Element, 1901. Find a Peak Element II
무한 루프를 피하기 위해서는 2개의 원소가 남았을 때를 고려해야 한다.

lower / upper mid를 잘못 선택하면 루프에서 아무 업데이트도 일어나지 않을 수 있고(= 축소가 일어나지 X), 이는 곧 무한 루프에 빠지게 된다.

프로그램이 무한 루프에 빠졌다면 lo와 hi로 설정된 경계 내부에 두 개의 요소만 남았을 때를 생각해야 한다.
- lower mid를 사용하는 다음의 코드는 두 개의 원소만 남았을 때 아무것도 하지 않아(= 자기자신으로 축소) 무한 루프에 빠지게 된다. 이러한 코드에서는 upper mid를 사용해야 한다.
```
mid = lo + (hi - lo) // 2 # lower mid

if target < nums[mid]:
    hi = mid - 1
else:
    lo = mid
```
- 반대로, upper mid를 사용하는 다음의 코드는 또한 무한 루프에 빠지게 된다. 이러한 코드에서는 lower mid를 사용해야 한다.
```
mid = lo + (hi - lo + 1) // 2 # upper mid

if target > nums[mid]:
    lo = mid + 1
else:
    hi = mid
```
704. Binary Search 문제를 다음과 같이 두 가지 mid를 모두 사용하여 풀 수 있다.

mid를 선택하는 것과 경계 축소 로직은 항상 함께 수행되어야 하며, 이때마다 최소 1개의 원소가 제외되어야 함을 명심한다.

가장 일반적인 템플릿

Minimize k, s.t. condition(k) is True

while loop 내의 if 문에서 비교연산자를 이용해서 판단해도 되지만, condition() 함수 안에서 boolean 값으로 판단해서 반환하면 더 깔끔하다!

단, 로직을 설계하기 어려울 수 있으니 우선 if 문에서 비교연산자를 이용하는 것도 좋을 것 같다.

def binary_search(array) -> int:
    def condition(value) -> bool:
        pass

    left, right = 0, len(array)
    while left < right:
        mid = left + (right - left) // 2
        if condition(mid):
            right = mid
        else:
            left = mid + 1
    return left

[!caution] condition 함수를 어떻게 설계해야 하고, 이를 만족하는 값 중 어떤 값을 찾아야 하는지를 잘 생각해야 한다.

(특히 k-th 원소를 찾는 문제와 같이 직관적이지 않은 경우...)

seungriyou / algorithm-study

[Algorithm] Binary Search 101 #98

References

이진 탐색(Binary Search)

이진 탐색 문제 풀이 시 고려해야 하는 세 가지

풀이 원칙

가장 일반적인 템플릿

Related Problems