이진 탐색

🧠 이진 탐색이란?

정렬된 리스트에서 원하는 값의 존재 여부 또는 위치를 빠르게 찾는 알고리즘

• 전제 조건: 데이터가 정렬되어 있어야 한다
• 매 탐색마다 탐색 범위를 절반으로 줄이기 때문에 효율적이다
• 시간 복잡도: O(log N)
• 구현 방식: 재귀, 반복문, 또는 C++ STL 사용

---

❓ 왜 이진 탐색이 필요한가?

• 순차 탐색(Linear Search)은 리스트의 길이가 N일 때, 최악의 경우 N번 비교
  • 시간 복잡도: O(N)
• 반면 이진 탐색은 매번 탐색 범위를 절반으로 줄이므로
  • 시간 복잡도: O(log N)
• 데이터가 많아질수록 효율의 차이가 커진다

---

🧩 작동 방식 (Divide and Conquer)

1. 리스트의 중간값(mid)을 확인한다
2. target이 중간값보다 작으면 왼쪽 절반 탐색
3. 크면 오른쪽 절반 탐색
4. 같으면 탐색 성공

이 방식은 분할 정복(Divide and Conquer) 알고리즘에 속한다
예) 숫자 맞추기 게임에서 항상 중간값을 선택하면 최소 시도로 정답을 찾을 수 있다

---

🔧 코드 구현 (C++)

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

vector<int> numbers;

void BinarySearch(int N)
{
    int left = 0;
    int right = (int)numbers.size() - 1;

    while (left <= right)
    {
        cout << "탐색 범위 : " << left << "~" << right << endl;

        // 중간값 계산 (오버플로우 방지)
        int mid = left + (right - left) / 2;

        if (N < numbers[mid])
        {
            right = mid - 1;
        }
        else if (N > numbers[mid])
        {
            left = mid + 1;
        }
        else
        {
            cout << "값 " << N << "을(를) 찾았습니다! 인덱스: " << mid << endl;
            return;
        }
    }

    cout << "값 " << N << "은 배열에 없습니다." << endl;
}

int main()
{
    numbers = vector<int>{ 1, 8, 15, 23, 32, 44, 56, 63, 81, 91 };
    BinarySearch(82);
    return 0;
}

---

🖥️ 출력 예시

탐색 범위 : 0~9
탐색 범위 : 5~9
탐색 범위 : 8~9
탐색 범위 : 9~9
값 82은 배열에 없습니다.

• 82는 32, 63, 81, 91과 비교되며, 그때그때 탐색 범위가 반씩 줄어든다
• 최종적으로 left > right가 되어 탐색이 종료된다

---

📦 배열 vs 트리

항목	배열	트리
삽입/삭제 성능	느림 (정렬 유지 필요)	빠름 (동적 구조)
이진 탐색 가능	가능 (정렬 필요)	불필요 (BST 구조로 바로 가능)
메모리 활용도	낭비 발생 가능	노드 단위 관리로 효율적
랜덤 접근	가능	불가능 (연결된 노드를 따라가야 함)

연결 리스트는 임의 접근이 불가능하므로 이진 탐색에 적합하지 않다

---