이진 탐색 정리

1. 반복적 방법

key값을 찾을 때까지 반복문은 탐색 범위를 반으로 줄이는 작업을 반복한다
정렬된 상태에서 수행 가능
key값을 갖는 원소가 여러 개 있을 때 원소들 중 어떤 원소의 인덱스를 반환할지 예측하기 힘들다
→ key값의 원소들 중 가장 작은 인덱스를 찾고 싶다면, 이진 탐색 후 반환된 인덱스에서 작은 인덱스 방향으로 다른 값이 나올 때까지 탐색하면 된다

최상의 경우 시간 복잡도
- key값을 가진 원소가 배열의 가운데에 있을 때
- 가운데 원소와 key 값을 한 번의 비교 후 탐색 완료 → $O(1)$
최악의 경우 시간 복잡도
- 탐색 범위를 더 이상 반으로 나눌 수 없을 때까지 줄여야 찾을 수 있는 인덱스에 key가 존재하는 경우
- 배열의 원소 개수 $N$을 2로 나눌 수 있는 횟수가 증가하면 수행 시간이 증가한다 → $O(\log_2N)$
공간 복잡도
- 원소 개수가 늘어나도 알고리즘 수행에 필요한 메모리 크기는 같다 → $O(1)$

시간 복잡도
- 1.3. 성능 의 시간 복잡도와 같다
최상의 경우 공간 복잡도
- key값을 가진 원소가 배열의 가운데에 있을 때
- 탐색 범위 크기에 상관없이 재귀 호출은 일어나지 않는다 → $O(1)$
촤악의 경우 공간 복잡도
- 탐색 범위를 반으로 나눌 수 없을 때까지 줄여야 찾을 수 있는 인덱스에 key가 존재하는 경우
- leftIdx와 rightIdx의 차를 2로 나눌 수 있는 횟수가 증가할 때 재귀 호출 횟수가 증가
- leftIdx를 $l$, rightIdx를 $r$이라고 할 때 공간 복잡도는 $O(\log_2(r - l))$