[C++로 배우는 알고리즘과 자료구조] Day 22: 이진 탐색 (Binary Search)

이진 탐색 (Binary Search)

이진 탐색은 정렬된 배열에서 원하는 값을 찾는 효율적인 알고리즘입니다. 배열의 중간 값을 선택하고, 중간 값과 찾고자 하는 값을 비교하여 검색 범위를 절반으로 줄여가며 탐색합니다.

이진 탐색의 시간 복잡도:

• 최선의 경우: (O(1))
• 평균의 경우: (O(\log n))
• 최악의 경우: (O(\log n))

이진 탐색 구현

이진 탐색은 재귀적으로 또는 반복적으로 구현할 수 있습니다.

 

재귀적 이진 탐색 구현

#include <iostream>
#include <vector>

// 재귀적 이진 탐색 함수
int binarySearchRecursive(const std::vector<int>& arr, int left, int right, int target) {
    if (right >= left) {
        int mid = left + (right - left) / 2;

        // 목표 값을 찾은 경우
        if (arr[mid] == target) {
            return mid;
        }

        // 목표 값이 중간 값보다 작은 경우
        if (arr[mid] > target) {
            return binarySearchRecursive(arr, left, mid - 1, target);
        }

        // 목표 값이 중간 값보다 큰 경우
        return binarySearchRecursive(arr, mid + 1, right, target);
    }

    // 목표 값을 찾지 못한 경우
    return -1;
}

int main() {
    std::vector<int> arr = {2, 3, 4, 10, 40};
    int target = 10;

    int result = binarySearchRecursive(arr, 0, arr.size() - 1, target);
    if (result != -1) {
        std::cout << "값 " << target << "는 인덱스 " << result << "에 있습니다." << std::endl;
    } else {
        std::cout << "값 " << target << "를 찾을 수 없습니다." << std::endl;
    }

    return 0;
}

 

반복적 이진 탐색 구현

#include <iostream>
#include <vector>

// 반복적 이진 탐색 함수
int binarySearchIterative(const std::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) {
            return mid;
        }

        // 목표 값이 중간 값보다 작은 경우
        if (arr[mid] > target) {
            right = mid - 1;
        } else { // 목표 값이 중간 값보다 큰 경우
            left = mid + 1;
        }
    }

    // 목표 값을 찾지 못한 경우
    return -1;
}

int main() {
    std::vector<int> arr = {2, 3, 4, 10, 40};
    int target = 10;

    int result = binarySearchIterative(arr, target);
    if (result != -1) {
        std::cout << "값 " << target << "는 인덱스 " << result << "에 있습니다." << std::endl;
    } else {
        std::cout << "값 " << target << "를 찾을 수 없습니다." << std::endl;
    }

    return 0;
}

 

설명

1. 재귀적 이진 탐색:
   • 배열의 중간 값을 선택하고, 중간 값과 목표 값을 비교하여 검색 범위를 절반으로 줄입니다.
   • 검색 범위가 더 이상 없을 때까지 재귀 호출을 반복합니다.
2. 반복적 이진 탐색:
   • 배열의 중간 값을 선택하고, 중간 값과 목표 값을 비교하여 검색 범위를 절반으로 줄입니다.
   • 검색 범위가 더 이상 없을 때까지 반복문을 실행합니다.

이진 탐색의 기본 개념과 구현 방법을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 자료구조와 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 23: 깊이 우선 탐색 (DFS)"에 대해 학습하겠습니다.