이진 탐색

1. 이진 탐색이란?

🌟 정의

• 정렬된 데이터에서 원하는 값을 찾기 위해 중간값과 비교하며 탐색 범위를 줄여가는 알고리즘.
• 데이터가 정렬되어 있다는 전제 조건 하에서만 동작합니다.

---

1-1. 작동 원리

1. 탐색 범위의 중간값을 선택.
2. 중간값과 찾고자 하는 값(N)을 비교:
   • 찾는 값이 중간값보다 작으면, 왼쪽 절반을 새로운 탐색 범위로 설정.
   • 찾는 값이 중간값보다 크면, 오른쪽 절반을 새로운 탐색 범위로 설정.
   • 찾는 값이 중간값과 같으면, 해당 값을 반환하고 탐색 종료.
3. 탐색 범위를 반복적으로 좁혀가며, 범위가 1개가 될 때까지 반복.

---

1-2. 시간 복잡도

• 탐색 대상이 매번 절반으로 줄어들기 때문에, 시간 복잡도는 O(log N).
• 예를 들어, 1024개의 데이터가 있다면:
  • 첫 번째 탐색: 1024 → 512
  • 두 번째 탐색: 512 → 256
  • ...
  • 10번 이내에 원하는 값을 찾을 수 있음.

---

2. 이진 탐색의 장단점

2-1. 장점

1. 효율적:
   • 선형 탐색(O(N))보다 훨씬 빠르게 작동.
   • 데이터 크기가 커질수록 더 큰 이점을 제공.
2. 공간 효율성:
   • 추가적인 공간을 요구하지 않음.

---

2-2. 단점

1. 정렬된 데이터 필요:
   • 이진 탐색은 정렬된 데이터에서만 작동.
   • 데이터가 정렬되어 있지 않다면, 추가적인 정렬 작업 필요 (O(N log N)).
2. 삽입/삭제 비효율적:
   • 배열 기반 컨테이너(std::vector)는 중간 삽입/삭제 시 O(N) 시간이 소요.
   • 삽입/삭제가 빈번하다면, std::map 또는 std::set과 같은 동적 데이터 구조가 더 적합.

---

3. 이진 탐색 구현

3-1. 코드

이진 탐색 함수

#include <iostream>
#include <vector>

std::vector<int> numbers;

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

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

        int mid = (left + right) / 2; // 중간값 계산
        if (N < numbers[mid]) {
            std::cout << N << " < " << numbers[mid] << std::endl;
            right = mid - 1; // 왼쪽 절반 탐색
        } else if (N > numbers[mid]) {
            std::cout << N << " > " << numbers[mid] << std::endl;
            left = mid + 1; // 오른쪽 절반 탐색
        } else {
            std::cout << "찾았음: " << numbers[mid] << std::endl;
            return;
        }
    }

    std::cout << "값을 찾지 못함." << std::endl;
}

main 함수

int main() {
    numbers = {1, 8, 15, 23, 32, 44, 56, 63, 81, 91}; // 정렬된 벡터

    BinarySearch(81); // 81을 찾는 탐색 실행
    return 0;
}

---

3-2. 코드 분석

1) 데이터 준비

numbers = {1, 8, 15, 23, 32, 44, 56, 63, 81, 91};

• 정렬된 벡터: 이진 탐색은 정렬된 데이터에서만 작동하므로, 벡터 numbers는 오름차순으로 정렬되어 있습니다.

---

2) 초기화

int left = 0;
int right = numbers.size() - 1;

• left: 탐색 범위의 시작 인덱스.
• right: 탐색 범위의 끝 인덱스. 초기값은 벡터 크기에서 1을 뺀 값.

---

3) 중간값 계산

int mid = (left + right) / 2;

• 현재 탐색 범위의 중앙 인덱스를 계산.
• 중간값은 (left + right) / 2.

---

4) 탐색 범위 조정

1. 찾는 값이 중간값보다 작은 경우:

   if (N < numbers[mid]) {
       right = mid - 1;
   }

   • 탐색 범위를 왼쪽 절반으로 축소.

2. 찾는 값이 중간값보다 큰 경우:

   else if (N > numbers[mid]) {
       left = mid + 1;
   }

   • 탐색 범위를 오른쪽 절반으로 축소.

3. 찾는 값을 발견한 경우:

   else {
       std::cout << "찾았음: " << numbers[mid] << std::endl;
       return;
   }

   • 중간값이 찾는 값과 같으면 탐색 종료.

4. 찾는 값이 없는 경우:

   • 반복문이 종료되면, 값이 없다는 메시지를 출력.

---

3-3. 실행 결과

탐색 범위: 0 ~ 9
81 > 32
탐색 범위: 5 ~ 9
81 > 63
탐색 범위: 8 ~ 9
81 == 81
찾았음: 81

---

4. 이진 탐색의 변형

1. 재귀적 이진 탐색:

   • 재귀를 사용하여 탐색 과정을 구현할 수 있습니다.

   int RecursiveBinarySearch(const std::vector<int>& arr, int left, int right, int target) {
       if (left > right) return -1;
   
       int mid = (left + right) / 2;
       if (arr[mid] == target) return mid;
       else if (arr[mid] > target) return RecursiveBinarySearch(arr, left, mid - 1, target);
       else return RecursiveBinarySearch(arr, mid + 1, right, target);
   }

2. 중복 값 처리:

   • 동일한 값이 여러 개 존재할 경우, 첫 번째 또는 마지막 값을 찾도록 변경 가능.

---

5. 이진 탐색과 선형 탐색 비교

특징	이진 탐색	선형 탐색
시간 복잡도	O(log N)	O(N)
데이터 정렬 여부	정렬 필수	정렬 불필요
탐색 속도	빠름	느림
삽입/삭제 효율성	비효율적	효율적

---