[c++] 배열과 포인터를 사용한 이진 탐색 구현

14 Dec 2023

이진 탐색은 정렬된 배열에서 특정한 항목을 찾는 데 사용되는 효율적인 알고리즘입니다. C++를 사용하여 배열과 포인터를 이용해 이진 탐색을 구현해보겠습니다.

배열과 이진 탐색

이진 탐색은 주어진 배열의 중간 값과 비교하여 탐색 범위를 반으로 줄여가는 과정을 통해 원하는 항목을 찾습니다. 이를 통해 O(log n)의 시간 복잡도를 가지며 매우 빠른 탐색이 가능합니다.

코드 구현

#include <iostream>

int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target)
            return mid;
        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1;
}

int main() {
    int arr[] = {2, 4, 6, 8, 10, 12, 14, 16};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 10;
    int result = binarySearch(arr, 0, n - 1, target);
    if (result == -1)
        std::cout << "원소를 찾을 수 없습니다.";
    else
        std::cout << "원소가 인덱스 " << result << " 에 있습니다.";
    return 0;
}

위의 코드에서 binarySearch 함수는 주어진 배열에서 이진 탐색을 수행합니다. main 함수에서는 이 함수를 활용하여 배열에서 특정한 값을 찾습니다.

포인터 활용

이진 탐색에서는 배열의 중간 값을 계산하여 비교하는데, 이때 포인터의 특성을 활용할 수 있습니다. 해당 배열의 주소에서 더하기나 빼기 연산을 통해 중간 값을 가져올 수 있습니다.

결론

C++를 사용하여 배열과 포인터를 활용한 이진 탐색 알고리즘을 구현해보았습니다. 배열과 포인터를 활용한 이진 탐색은 효율적이고 빠른 탐색 알고리즘 중 하나입니다. 여러 가지 상황에서 유용하게 활용될 수 있으며, 이를 통해 C++ 프로그래밍에 대한 이해를 높일 수 있습니다.

배열과 이진 탐색

코드 구현

포인터 활용

결론

참고 자료