분할 정복 : 이진 탐색 (Binary Search)

---

📌 예제 코드

#include <iostream>
#include <vector>
using namespace std;

// 이진 탐색 함수
int binarySearch(vector<int>& arr, int left, int right, int target) {
    if (left > right) return -1;  // 기저 사례 (못 찾으면 -1 반환)
    
    int mid = (left + right) / 2;  // 중간 인덱스 찾기
    if (arr[mid] == target) return mid;  // 찾았다!
    else if (arr[mid] > target) return binarySearch(arr, left, mid - 1, target);  // 왼쪽 탐색
    else return binarySearch(arr, mid + 1, right, target);  // 오른쪽 탐색
}

int main() {
    vector<int> arr = { 1, 3, 5, 7, 9, 11, 13, 15 };  // 정렬된 배열
    int target = 9;  // 찾을 값

    int index = binarySearch(arr, 0, arr.size() - 1, target);
    if (index != -1) cout << "숫자 " << target << "는 인덱스 " << index << "에 있습니다!\n";
    else cout << "찾는 숫자가 없습니다.\n";

    return 0;
}

---

🎯 실행 과정 (배열: {1, 3, 5, 7, 9, 11, 13, 15}에서 9 찾기!)

✅ 배열의 인덱스

0   1   2   3   4   5   6   7
1   3   5   7   9   11  13  15

---

🚀 1️⃣ 첫 번째 탐색 (mid = (0+7)/2 = 3)

• 중간값: arr[3] = 7
• 7 < 9 → 오른쪽에서 찾기
• 새로운 범위: [4 ~ 7]

---

🚀 2️⃣ 두 번째 탐색 (mid = (4+7)/2 = 5)

• 중간값: arr[5] = 11
• 11 > 9 → 왼쪽에서 찾기
• 새로운 범위: [4 ~ 4]

---

🚀 3️⃣ 세 번째 탐색 (mid = (4+4)/2 = 4)

• 중간값: arr[4] = 9
• 9 == 9 ✅ 찾았다! (인덱스 4 반환)

---

✅ 실행 결과

숫자 9는 인덱스 4에 있습니다!

---

🎯 핵심 요약

단계 중간값(mid) 비교 결과 탐색 범위 변경

1️⃣	arr[3] = 7	7 < 9 → 오른쪽 탐색	[4 ~ 7]
2️⃣	arr[5] = 11	11 > 9 → 왼쪽 탐색	[4 ~ 4]
3️⃣	arr[4] = 9	9 == 9 → 찾음!	✅

---

📌 이진 탐색의 장점

✅ O(log N) 속도로 매우 빠름! (ex: 1,000,000개 데이터도 약 20번 만에 탐색 가능)
✅ 데이터가 정렬되어 있을 때 가장 효율적
✅ 정렬이 안 되어 있으면 반드시 먼저 정렬해야 함!

---

📌 정리

✅ 이진 탐색은 정렬된 배열에서 원하는 값을 빠르게 찾는 알고리즘!
✅ 매 단계마다 탐색 범위를 반으로 줄이므로 O(log N)의 빠른 성능!
✅ 정렬되지 않은 배열에서는 사용 불가! (먼저 sort() 필요)