# 이진 탐색

**이진 탐색(binary search)**을 사전에서는 "검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘"이라고 정의하고 있습니다. 하지만 사전적 의미는 잘 와닿지 않으니, 한 가지 예시를 들어보겠습니다.

## 업다운 게임

```python
import random
num = random.randrange(1, 101)
# num == 25 이라고 가정하겠습니다.
```

1부터 100까지의 자연수 중에서 이 num(25)를 맞추는데 최소 몇 번의 시도를 해야할까요?

**완전 탐색**을 기억해보면, 우리는 최악의 경우 100번의 시도를 해야합니다. 그렇기 때문에 시간 복잡도는 **O(N)**이죠.

하지만 이 고정된 num 값과 우리가 시도한 숫자의 대소 관계를 파악할 수 있다면 더 빠르게 num 값을 알아낼 수 있습니다. [<mark style="background-color:yellow;">**업다운 게임**</mark>](https://up-down-game-gyuri.netlify.app/)을 생각하시면 됩니다. ~~해당 링크에 들어가서 한 번 해보세요 !~~

우리가 50 ! 을 외치면, num이 50보다 작다는 사실을 알게 되므로 51부터 100까지의 수는 정답의 범위에서 배제됩니다.

이처럼, 1\~100까지의 수에서 우리가 원하는 수를 알기 위해서는 최대 7번만 시도하면 됩니다. 따라서 정렬된 상황에서 특정 수를 조회하는 시간 복잡도는 **O(logN)**&#xC785;니다. 리스트가 아직 정렬되어있지 않아 정렬이 필요하다면,  **O(NlogN)**&#xC758; 시간 복잡도로 정렬한 후 이분탐색을 진행해주면 됩니다.

위의 상황을 코드로 나타내면 아래와 같습니다.

```python
num = 25
left = 1
right = 100
while left <= right:
    mid = (left + right) // 2

    if mid == num:
        break
    elif mid < num:
        left = mid + 1
    elif mid > num:
        right = mid - 1
```

처음 수의 범위를 **left \~ right**로 설정하고, 조건에 맞게 범위를 좁혀가는 방식으로 진행됩니다.

그러다 **left**가 **right**를 넘어설 경우에 반복문은 종료됩니다.

## upper bound, lower bound

이분 탐색의 핵심은 \
\|-----------------ㅇ-----| 명확히 나누어지는 이 **경계값** 을 찾는 것입니다.&#x20;

하지만 같은 숫자가 여러 번 존재하는 배열이라면 어떻게 숫자의 위치를 찾을 수 있을까요?

이는 upper bound와 lower bound 개념으로 이해할 수 있습니다.

```python
파이썬 upper bound, lower bound
def lowerbound(array, k): # k 이상 값이 처음 나오는 위치
    left = 0
    right = len(array)

    while left < right:
        mid = (left + right) // 2

	# 📢 이 부분 주의!
        if array[mid] >= k: #오른쪽으로 좁힘 -> upperbound
            right = mid
        else:
            left = mid + 1

    return left
def upperbound(array, k): #k 초과 값이 처음 나오는 위치
    left = 0
    right = len(array)
    
    while left < right:
        mid = (left + right) // 2
		
        # 📢 이 부분 주의!
        if array[mid] > k:
            right = mid
        else:
            left = mid + 1

    return left  
    
lowerbound([0,1,2,4,4,4,7,8], 4) #3 return
upperbound([0,1,2,4,4,4,7,8], 4) #6 return
```

<figure><img src="https://1655951078-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FsEvqqxs7B4iBGzqaDFYQ%2Fuploads%2FO84SNJn0Sdn8HaSpQ57Q%2Fimage.png?alt=media&#x26;token=c6706b18-daa2-4b0c-aada-91dc46f051bd" alt=""><figcaption></figcaption></figure>

조금 더 생각해볼까요? 왜 lowerbound와 upperbound를 만족하는지 꼭 ! 직접 설명해볼 수 있을 때까지 이해하고 넘어가봅시다.

* lowerbound 로직 \
  right = mid 로 할당하는 건 범위를 왼쪽으로 좁히는 것을 의미합니다.\
  이 때 array\[mid]가 k랑 같아도 right=mid로 왼쪽으로 계속 좁히기 때문에 lowerbound를 만족시키게 됩니다.
* upperbound 로직 \
  array\[mid]가 k와 같거나 작을 때까지 left = mid+1로 계속 오른쪽으로 보냅니다.\
  따라서 left는 만족을 하게 되는 때가 오더라도 그 뒷 값을 가리키게 됩니다. 즉, upperbound를 만족시킵니다.

##

## 연습문제

### BOJ 13423

{% embed url="<https://www.acmicpc.net/problem/13423>" %}

바로 이전의 완전 탐색 파트에서 다뤘던 문제입니다.

완전 탐색으로도 가능하지만, **이진 탐색** 또한 풀이가 가능한 문제입니다.

참고로 해당 풀이는 pypy3에만 적용됨을 참고해주시기 바랍니다.

```python
t = int(input())
for _ in range(t):
    n = int(input())
    li = sorted(list(map(int, input().split())))
    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):   # 중복되는 인덱스가 없도록 i+1부터 시작
            left = i
            right = j
            val = (li[left] + li[right]) / 2    # 원하는 값
            while left <= right:
                mid = (left + right) // 2
                if val == li[mid]:
                    ans += 1
                    break
                elif val > li[mid]:
                    left = mid + 1
                elif val < li[mid]:
                    right = mid - 1
    print(ans)
```

이전에 해당 문제를 **완전 탐색**으로 접근할 때의 컨셉을 그대로 따라해봅시다.

일단 마찬가지로 두 점을 반복문을 통해 고릅니다. **완전 탐색**에서는 첫 번째, 두 번째 점을 골랐으니 이번엔 첫 번째와 세 번째 점을 골라보도록 합시다.&#x20;

각 점의 인덱스를 left, right로 지정하고, 우리가 원하는 중앙 값(val)이 리스트에 있는지만 확인해주면 됩니다.

같은 문제를 여러 방식으로 푸는 것도 많은 도움이 되니, 꼭 풀어보시길 바랍니다.

## 풀어볼 문제

이진탐색 또한 시간복잡도에 주의하며 문제를 풀어봅시다.

{% embed url="<https://www.acmicpc.net/problem/16401>" %}
16401
{% endembed %}

{% embed url="<https://www.acmicpc.net/problem/17951>" %}
17951
{% endembed %}

(cf. 17951 문제처럼 정렬을 하지 않아야하는 **이진 탐색** 문제도 있으니 유의하세요!)

{% embed url="<https://www.acmicpc.net/problem/17179>" %}
17179
{% endembed %}