[c++] 이진 탐색 알고리즘

12 Dec 2023

이진 탐색은 정렬된 배열에서 특정한 값을 찾는 효율적인 알고리즘입니다. 이 알고리즘은 배열의 중간 요소를 선택하고 찾으려는 값과 비교하여, 찾으려는 값이 중간 요소보다 작은지 큰지를 판단합니다. 그런 다음 찾으려는 값을 찾을 때까지 배열을 계속해서 반으로 나누는 작업을 반복하며 값을 탐색하는 방식입니다.

알고리즘 동작 방식

시작점, 끝점 및 중간점을 설정합니다.
중간점의 값과 찾으려는 값의 비교를 수행합니다.
작으면, 중간점을 기준으로 왼쪽 부분을 대상으로 다시 탐색합니다.
크면, 중간점을 기준으로 오른쪽 부분을 대상으로 다시 탐색합니다.
값을 찾을 때까지 위의 과정을 반복합니다.

아래는 C++로 작성된 이진 탐색 알고리즘의 예시입니다.

#include <iostream>
#include <vector>

int binarySearch(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;
}

int main() {
    std::vector<int> numbers = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int target = 23;
    int result = binarySearch(numbers, target);
    std::cout << "Element found at index: " << result << std::endl;
    return 0;
}

위 코드는 정렬된 배열에서 특정 값을 검색하는 이진 탐색 알고리즘을 구현한 예시입니다.

결론

이진 탐색 알고리즘은 정렬된 배열에서 값을 효율적으로 검색하는 방법으로, 탐색 시간을 로그 시간 복잡도 O(log n)로 줄일 수 있습니다.

참고문헌:

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT press.