Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 이진 검색(Binary Search) 완벽 가이드: 개념부터 재귀 구현까지

이진 검색(Binary Search)은 정렬된 배열에서 원하는 요소를 찾기 위해 배열을 반복적으로 절반으로 나누며 탐색 범위를 좁혀 가는 알고리즘입니다. 선형 검색이 모든 요소를 하나씩 확인하는 것과 달리, 이진 검색은 매 단계마다 탐색 대상을 절반으로 줄이므로 매우 빠른 속도를 자랑합니다.

이진 검색의 동작 원리

이진 검색은 전체 배열에서 시작합니다. 먼저 배열의 중앙에 있는 요소와 찾고자 하는 값을 비교하는데, 찾으려는 값이 중앙 요소보다 크면 배열의 상위 절반을, 작으면 하위 절반을 탐색 대상으로 삼습니다.

이 과정은 다음 두 가지 경우 중 하나가 발생할 때까지 계속됩니다.

  • 찾고자 하는 데이터 값을 발견한 경우
  • 남은 탐색 범위가 비어 있는 경우(값이 존재하지 않음)

이진 검색의 시간 복잡도는 O(log n)으로, 배열의 크기가 커져도 탐색 횟수가 로그 스케일로만 증가하기 때문에 대용량 정렬 데이터에서 특히 효과적입니다.

C++ 이진 검색 예제 코드

아래 프로그램은 재귀 함수를 사용해 C++에서 이진 검색을 구현한 예제입니다.

#include <iostream>
using namespace std;

int binarySearch(int arr[], int p, int r, int num) {
    if (p <= r) {
        int mid = (p + r) / 2;
        if (arr[mid] == num)
            return mid;
        if (arr[mid] > num)
            return binarySearch(arr, p, mid - 1, num);
        if (arr[mid] < num)
            return binarySearch(arr, mid + 1, r, num);
    }
    return -1;
}

int main(void) {
    int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int num;
    cout << "Enter the number to search: \n";
    cin >> num;
    int index = binarySearch(arr, 0, n - 1, num);
    if (index == -1) {
        cout << num << " is not present in the array";
    } else {
        cout << num << " is present at index " << index << " in the array";
    }
    return 0;
}

실행 결과

Enter the number to search
20
20 is present at index 5 in the array

코드 상세 설명

binarySearch() 함수

위 프로그램에서 binarySearch()는 이진 검색 방식으로 배열에서 원하는 요소를 찾는 재귀 함수입니다. 이 함수는 배열, 배열의 하한(lower bound)과 상한(upper bound), 그리고 찾고자 하는 숫자를 매개변수로 받습니다.

int binarySearch(int arr[], int p, int r, int num)

함수 내부의 동작 흐름은 다음과 같습니다.

  1. 먼저 배열의 중간 지점(midpoint)을 계산합니다.
  2. 중간 지점의 값이 num과 같으면 해당 인덱스를 반환합니다.
  3. 중간 값이 num보다 크면, 하한 p와 상한 mid-1로 자기 자신을 재귀 호출하여 하위 절반을 탐색합니다.
  4. 중간 값이 num보다 작으면, 하한 mid+1과 상한 r로 재귀 호출하여 상위 절반을 탐색합니다.
int binarySearch(int arr[], int p, int r, int num) {
    if (p <= r) {
        int mid = (p + r) / 2;
        if (arr[mid] == num)
            return mid;
        if (arr[mid] > num)
            return binarySearch(arr, p, mid - 1, num);
        if (arr[mid] < num)
            return binarySearch(arr, mid + 1, r, num);
    }
    return -1;
}

하한이 상한보다 커지면(p > r) 더 이상 탐색할 범위가 없다는 뜻이므로, 함수는 값을 찾지 못했다는 의미로 -1을 반환합니다.

main() 함수

main() 함수에서는 배열 arr[]을 정의하고, sizeof 연산자를 이용해 배열의 크기를 계산한 뒤 찾고자 하는 숫자를 입력받습니다. 이후 binarySearch()를 호출해 해당 숫자의 인덱스를 구합니다.

int main(void) {
    int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int num = 33;
    int index = binarySearch(arr, 0, n - 1, num);
    if (index == -1)
        cout << num << " is not present in the array";
    else
        cout << num << " is present at index " << index << " in the array";
    return 0;
}

binarySearch()가 반환한 값이 -1이면 해당 숫자가 배열에 존재하지 않는 것이고, 그렇지 않으면 반환된 인덱스 위치에 숫자가 존재하는 것입니다.

마무리

이진 검색은 정렬된 데이터에서 원하는 값을 빠르게 찾는 가장 기본적이면서도 강력한 알고리즘입니다. 재귀 방식 외에도 while 문을 활용한 반복(iterative) 방식으로 구현할 수 있으며, C++ 표준 라이브러리(STL)에서는 std::binary_search, std::lower_bound 등의 함수로도 제공되므로 실무에서 손쉽게 활용할 수 있습니다.