🌓 이진탐색

💫 정의

---

이진탐색 Binary-Search
정렬된 리스트에 대해, 특정 원소의 위치를 찾아내는 알고리듬

💫 왜 Why

---

🫧 탐색 문제

• 전화번호부에서 이름이 K로 시작하는 사람의 번호 찾기
  • 첫 페이지부터 한 장씩 차례대로 넘기면서 찾는 방법
  • 책 한가운데를 펼치고 찾기 시작하는 방법
    • 알파벳 순서대로라면 중간쯤에 K로 시작하는 이름이 있을 테니까
• 사전에서 단어 찾기
• 페이스북에 로그인하기 (페이스북이 내 계정이 실존하는 계정인지 확인하기 위해 데이터베이스에서 아이디 찾기)

🫧 vs 단순 탐색 Single-Search

단순 탐색 Single-Search, 순서대로 탐색
한 번 추측할 때마다 추측한 숫자 하나가 답이 아니라는 것을 알게 될 뿐
1~100 숫자에 대해, 만약 답이 99이라면 답에 도달하기 까지 99번 추측해야 한다

더 좋은 방법

100의 중간 50부터 시작하는 것
50이 너무 작다 는 대답 하나로 숫자의 절반이 답이 아니라는 것을 알 수 있다
남은 51~100 까지의 숫자 중 중간에 속하는 75로 추측
75가 너무 크다는 것을 알았으므로 앞에서와 마찬가지로 이 숫자보다 같거나 큰 숫자들을 제외할 수 있다

이진 탐색에서는 매번 남은 숫자 중의 가운데 숫자를 말하고 대답에 따라 그보다 큰 숫자 혹은 작은 숫자들을 한꺼번에 없앨 수 있습니다.

100개의 숫자 최대 7번 만에 정답을 맞출 수 있다
240,000개 단어 최대 18단계 안에 찾을 수 있다
단순 탐색으로는 240,000번

n개의 원소를 가진 리스트에서 이진 탐색으로 사용하면 최대 log₂n번 만에 답을 찾을 수 있다.

단순 탐색이면 최대 n번이 필요할 수도 있다.
리스트에 숫자 8개 있다면 최악의 경우 8개의 숫자를 모두 확인해봐야 한다는 말

이진 탐색을 사용하면 최악의 경우에도 log n개의 숫자만 확인하면 됩니다. 리스트에 숫자가 8개 있다면 2³ = 8, 즉 log 8 = 3 이므로 3번만 확인해도 됩니다. 원소가 1,024개이면 2^{10 = 1,024, 즉 log 1,024 = 10 이므로 숫자 10개만 확인해도 충분합니다.}

💫 구현

---

처음에는 모든 범위를 탐색
이후 (low + high) / 2, 절반씩 범위를 줄여 나가는
(문제, low + high가 짝수면 괜찮은데, 홀수일 경우에는? 결과 값 내림)
재귀 함수