# Chapter 2: 이진 탐색

## 내용 정리

### 선형 스캔

* 탐색 방식
  * list에서 한 번에 하나씩 값을 비교하면서 목푯값을 찾거나, 목록의 끝에 도달할 때까지 비교해 목푯값을 찾는다
* 단점
  * 원소가 아주 많은 리스트에서 비효율적이다

### 이진 탐색 알고리즘

* 탐색 방식
  * list를 반으로 분할하고, 목푯값이 어느쪽 절반에 속하는지 결정한다
  * 목푯값이 포함되지 않는 절반을 버리고, 여전히 목푯값이 있을 수 있는 나머지 절반만 가지고 같은 과정을 반복해 마지막 값만 남을때까지 이를 반복한다
* 특징
  * 정렬된 데이터에서만 작동한다
  * 배열이 오름차순으로 정렬되어 있음을 이용한다
  * 두 경계를 이용해 탐색 공간을 추적한다
    * upper bound → index high
    * lower bound → index low
  * index low가 목푯값을 가리키게 되어도, 중간 지점이 목푯값을 가리킬 때까지 탐색을 계속한다
* 없는 값 처리
  * 목푯값이 리스트에 없는 경우 탐색을 계속 진행하다 보면, 두 경계 중 하나가 항상 중간 index를 넘어가기 때문에 index high < index low 가 되면 탐색을 중단할 수 있다
* 구현

  ```python
  def binary_search(array: list[int], target: int) -> int:
    start, end = 0, len(array) - 1

    while start <= end:
      mid = (start + end) // 2

      if array[mid] == target:
        return mid
      elif array[mid] < target:
        start = mid + 1
      else:
        end = mid - 1

    return -1
  ```
* index 나 이산적인 원소 집합이 존재하지 않는 연속 데이터에 적용
  * 탐색 방식
    * index 대신 값에 대한 upper bound와 lower bound를 이용
    * 범위가 작아질 때 탐색을 종료
      * upper bound - lower bound < threshold
  * 시사점
    * 선형 스캔보다 더 나은 정밀도를 얻을 수 있다
    * 이분법 (bisection search) 등의 수학적 기술의 기초가 된다
      * 이분법은 f(x) = 0인 x 값을 찾기 위해 사용하는데, 0보다 크거나 작은 경계를 추적한다
      * 중앙값에서 구간을 반복하여 절반으로 나눔으로써, 이분법 알고리즘은 함수가 정확히 0이 되는 x값에 접근할 수 있따
* 실행 시간

  |       | Time Complexity | Space Complexity           |
  | ----- | --------------- | -------------------------- |
  | 선형 스캔 | O(n)            | O(1)                       |
  | 이진 탐색 | O(log⁡ n)       | O(1) → 반복문 / O(log⁡n) → 재귀 |

  단, 이진 탐색은 정렬되지 않은 경우 데이터 정렬이 먼저 필요하므로 O(n log n)의 추가 비용 발생

## 생각

* 오늘 leetcode 에서 [binary search 문제](https://leetcode.com/problems/koko-eating-bananas/description/?envType=study-plan-v2\&envId=leetcode-75) 풀었는데 이 내용이 책에 나와서 재밌었다
* 자세히 살펴볼 수 있어 좋았다