> For the complete documentation index, see [llms.txt](https://koalas-organization.gitbook.io/koala_codingtest_study/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://koalas-organization.gitbook.io/koala_codingtest_study/search/binary_search.md).

# 이진 탐색

**이진 탐색(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="/files/1JEr3lUhpjfAiqZsSvvg" 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 %}


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://koalas-organization.gitbook.io/koala_codingtest_study/search/binary_search.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.