[c++] 바이너리 서치 알고리즘

15 Dec 2023

바이너리 서치 알고리즘은 정렬된 배열에서 원하는 값을 빠르게 찾는 효율적인 방법입니다. 이 알고리즘은 배열을 반으로 나누어 탐색 범위를 좁혀나가는 방식으로 동작합니다.

알고리즘 원리

배열을 정렬한다.
시작점, 끝점, 중간점을 정의한다.
중간점의 값과 찾고자 하는 값과 비교한다.
중간점의 값이 찾고자 하는 값보다 작으면 시작점을 중간점으로 이동시키고, 중간점의 값이 찾고자 하는 값보다 크면 끝점을 중간점으로 이동시킨다.
시작점과 끝점이 같아질 때까지 반복한다.

C++ 코드 예제

#include <iostream>
#include <vector>
#include <algorithm>

int binarySearch(std::vector<int>& arr, int target) {
    int start = 0;
    int end = arr.size() - 1;

    while (start <= end) {
        int mid = (start + end) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return -1;
}

int main() {
    std::vector<int> arr = {2, 4, 7, 10, 15, 20, 25, 30};
    int target = 15;

    int result = binarySearch(arr, target);
    if (result != -1) {
        std::cout << "Element found at index " << result << std::endl;
    } else {
        std::cout << "Element not found" << std::endl;
    }

    return 0;
}

참고 자료

바이너리 서치 알고리즘은 수많은 데이터를 빠르게 탐색할 수 있는 강력한 도구입니다. C++에서는 이 알고리즘을 활용하여 배열에서 원하는 값을 효율적으로 찾을 수 있습니다.