[c++] 반복문을 사용한 이진탐색 구현

07 Dec 2023

이진탐색은 배열이나 리스트와 같은 정렬된 데이터 구조에서 사용되는 효율적인 탐색 알고리즘입니다. 이진탐색을 반복문을 사용하여 구현할 수 있습니다. 반복문을 사용한 이진탐색 알고리즘의 구현을 살펴보겠습니다.

이진탐색 알고리즘

이진탐색 알고리즘은 탐색하고자 하는 데이터가 정렬되어 있다는 가정하에 작동합니다. 탐색할 데이터의 중간값을 선택하여 찾고자 하는 값과 비교합니다. 찾고자 하는 값과 중간값이 같다면 탐색을 완료합니다. 만약 중간값이 찾고자 하는 값보다 작다면 왼쪽 부분에 대해서만 탐색하고, 값이 크다면 오른쪽 부분에 대해서만 탐색합니다.

C++를 이용한 반복문을 사용한 이진탐색 구현

다음은 C++를 이용한 반복문을 사용한 이진탐색 알고리즘의 구현 예시입니다. 코드의 주석을 통해 각 부분의 역할을 설명하겠습니다.

#include <iostream>
#include <vector>

int binarySearch(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;  // 찾고자 하는 값이 중간값과 같다면 인덱스를 반환합니다.
        }
        else if (arr[mid] < target) {
            left = mid + 1;  // 중간값보다 찾고자 하는 값이 크다면 오른쪽 부분에서 탐색합니다.
        }
        else {
            right = mid - 1;  // 중간값보다 찾고자 하는 값이 작다면 왼쪽 부분에서 탐색합니다.
        }
    }
    return -1;  // 찾고자 하는 값이 배열 안에 존재하지 않을 경우 -1을 반환합니다.
}

int main() {
    std::vector<int> arr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int target = 14;
    int result = binarySearch(arr, target);
    if (result != -1) {
        std::cout << "Element found at index " << result << std::endl;
    }
    else {
        std::cout << "Element not found in the array" << std::endl;
    }
    return 0;
}

위의 예시는 정렬된 정수 배열에서 반복문을 사용하여 이진탐색을 수행하는 C++ 코드입니다. 입력된 배열에서 타겟 값의 인덱스를 반환하거나, 타겟 값이 존재하지 않는다면 -1을 반환합니다.

이진탐색은 계속해서 중간값을 찾아가므로 시간복잡도는 O(log n)으로 매우 효율적인 알고리즘이라고 할 수 있습니다.

이처럼 C++를 이용하여 반복문을 사용한 이진탐색을 구현할 수 있습니다.

마무리

반복문을 사용한 이진탐색은 이진탐색 알고리즘의 기본적인 원리를 활용하여 구현된 것으로, 정렬된 데이터 구조에서 탐색을 진행하고자 할 때 유용하게 활용됩니다. C++과 같은 언어를 활용하여 이진탐색을 구현할 수 있으며, 이를 통해 데이터 탐색의 성능을 획기적으로 향상시킬 수 있습니다.

이진탐색에 대한 더 많은 정보를 얻고자 한다면 이진탐색에 대한 위키백과 문서를 참고할 수 있습니다.