자료구조&알고리즘/C++

이분 탐색 //(Binary Search)

geminanolja 2025. 1. 22. 11:09

**이분탐색(Binary Search)**은 정렬된 배열에서 탐색 범위를 절반씩 줄여나가는 방식으로 특정 값을 찾는 알고리즘

시간 복잡도는 O(log N)**이며, 이진탐색이라고도 부름

문제에서 주어진 배열의 크기가 너무 크거나 어떤 값을 찾아야 하는 로직이 있을 때, 해당 배열을 정렬하고 이분탐색을 사용하면 **O(log N)**의 시간복잡도로 효율적으로 값을 찾을 수 있다

이분탐색의 동작 원리

  1. 초기 설정:
    • 배열의 가장 왼쪽 인덱스 left와 가장 오른쪽 인덱스 right를 설정
  2. 중간값 계산:
    • 현재 배열의 중간 인덱스 mid를 계산합니다.
    • 중간 인덱스는 mid = (left + right) / 2로 계산됩니다.
  3. 비교:
    • 목표값과 중간값이 같을 때:
      • 중간 인덱스 mid에 위치한 값이 목표값(target)과 일치하면 탐색을 종료하고 mid를 반환
    • 목표값이 중간값보다 작을 때:
      • 목표값이 중간값보다 작다면, 오른쪽 절반은 탐색할 필요가 없으므로 right = mid - 1로 설정하여 왼쪽 절반만 탐색
    • 목표값이 중간값보다 클 때:
      • 목표값이 중간값보다 크다면, 왼쪽 절반은 탐색할 필요가 없으므로 left = mid + 1로 설정하여 오른쪽 절반만 탐색
  4. 반복:
    • 이 과정을 목표값을 찾거나 left가 right보다 커질 때까지 반복
    • 만약 목표값을 찾지 못하면 일반적으로 -1 또는 배열의 범위에 해당하지 않는 숫자로 반환

정리된 핵심

  1. 시간복잡도: O(log N)
  2. 사용 조건: 배열이 정렬되어 있어야 함
  3. 동작 원리:
    • 범위를 절반씩 줄여나가며 특정 값을 탐색
  4. 반환값:
    • 목표값을 찾으면 해당 인덱스를 반환
    • 목표값이 없으면 -1을 반환하거나 별도의 처리를 수행

 

#include <bits/stdc++.h> // C++ 표준 라이브러리 헤더
using namespace std;

// **이진 탐색 함수**
// 입력: 정렬된 배열(arr), 찾고자 하는 값(target)
// 출력: target의 인덱스 (찾지 못하면 -1)
int binarySearch(const vector<int>& arr, int target) {
    int left = 0;                  // 탐색 범위의 왼쪽 끝 인덱스
    int right = arr.size() - 1;    // 탐색 범위의 오른쪽 끝 인덱스

    // 왼쪽 포인터가 오른쪽 포인터보다 작거나 같을 때까지 반복
    while (left <= right) {
        int mid = left + (right - left) / 2; // 중간 인덱스 계산 (오버플로 방지)

        if (arr[mid] == target) { // 중간값이 target과 같을 경우
            return mid; // target의 인덱스를 반환
        } else if (arr[mid] < target) { // 중간값이 target보다 작은 경우
            left = mid + 1; // 탐색 범위를 오른쪽으로 좁힘
        } else { // 중간값이 target보다 큰 경우
            right = mid - 1; // 탐색 범위를 왼쪽으로 좁힘
        }
    }
    return -1; // target을 찾지 못한 경우 -1 반환
}

int main() {
    // **입력 배열 정의 (오름차순으로 정렬된 상태)**
    vector<int> arr = {1, 3, 6, 9, 10, 21, 22, 30}; // 탐색 대상 배열
    int target = 6; // 찾고자 하는 값(target)

    // **이진 탐색 수행**
    int result = binarySearch(arr, target);

    // **결과 출력**
    if (result != -1) { // target을 찾았을 경우
        cout << "Target found at index: " << result << "\n"; // 인덱스 출력
    } else { // target을 찾지 못했을 경우
        cout << "Target not found in the array\n"; // 에러 메시지 출력
    }

    return 0; // 프로그램 종료
}

주석 요약

  1. binarySearch 함수
    • 정렬된 배열에서 이진 탐색을 수행하는 함수.
    • 중간값(mid)을 기준으로 탐색 범위를 절반씩 좁혀가며 target을 찾습니다.
    • 찾으면 인덱스를 반환, 찾지 못하면 -1 반환.
  2. main 함수
    • 배열 arr와 목표값 target을 정의.
    • 이진 탐색 함수 호출 후 결과를 출력.

출력 예제

입력

배열: {1, 3, 6, 9, 10, 21, 22, 30}
target: 6

출력

Target found at index: 2

코드 동작 설명

  1. 배열 arr와 목표값 target을 입력받습니다.
  2. 이진 탐색을 수행하여 target의 인덱스를 찾습니다.
  3. 찾으면 인덱스를 출력하고, 찾지 못하면 "Target not found" 메시지를 출력합니다.

이분탐색의 시간복잡도 증명 요약

이분탐색 과정

  • 탐색 대상 배열의 크기를 NN이라고 하면, 이분탐색은 배열을 매 단계마다 절반씩 줄이며 탐색을 진행합니다.
  • 탐색 범위는 다음과 같이 감소합니다:

  • 최악의 경우 탐색 범위가 1이 될 때까지 탐색을 반복합니다.

시간복잡도 증명

  1. 탐색 범위 표현:
    • k번째 단계에서 탐색 범위는 N/2k입니다
  2. 결론:
    • 탐색이 종료되기 위해 필요한 단계 수 k는 log⁡2(N)과 같습니다.
    • 따라서, **이분탐색의 시간복잡도는 O(log⁡N)입니다.

예제: 배열 길이가 16일 때

  1. 1단계:
    • 배열 크기 16 → 중간값을 비교 후 탐색 범위를 8로 줄임.
  2. 2단계:
    • 배열 크기 8 → 중간값을 비교 후 탐색 범위를 4로 줄임.
  3. 3단계:
    • 배열 크기 4 → 중간값을 비교 후 탐색 범위를 2로 줄임.
  4. 4단계:
    • 배열 크기 2 → 중간값을 비교 후 탐색 범위를 1로 줄임.

총 4단계 (log⁡2(16)=4\log_2(16) = 4)로 탐색이 완료됩니다.

결론

  • 이분탐색의 시간복잡도는 O(log⁡N)입니다.
  • 배열의 크기가 N일 때, 최악의 경우 log⁡2(N)단계 안에 탐색이 완료됩니다.