[c++] 이진 검색(Binary Search) 알고리즘

08 Dec 2023

이진 검색은 정렬된 배열에서 특정한 원소를 찾는 알고리즘입니다. 배열의 중간 원소와 비교하여 원하는 원소를 찾아가는 방식으로 동작합니다.

알고리즘 설명

시작점과 끝점을 정의합니다. (시작점: left = 0, 끝점: right = 배열의 길이 - 1)
중간 원소를 찾습니다. (중간 원소: mid = (left + right) / 2)
중간 원소와 찾고자 하는 원소를 비교합니다.
- 중간 원소가 찾고자 하는 원소와 같다면, 탐색 성공.
- 중간 원소보다 찾고자 하는 원소가 작으면, 범위를 왼쪽 반으로 좁힙니다. (right = mid - 1)
- 중간 원소보다 찾고자 하는 원소가 크면, 범위를 오른쪽 반으로 좁힙니다. (left = mid + 1)
2~3단계를 반복하여 원소를 찾습니다.

예시

다음은 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> arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int target = 11;

    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;
}

시간 복잡도

이진 검색 알고리즘의 시간 복잡도는 O(log n)입니다. 배열의 크기에 비례하여 시간이 증가하는 선형 검색보다 비교적 효율적인 알고리즘입니다.

이진 검색을 사용하면서 주의할 점은 정렬된 배열에서만 사용 가능하다는 것입니다.

결론

이진 검색 알고리즘은 정렬된 배열에서 원소를 찾는 데에 사용되며, 시간 복잡도가 낮아 많은 데이터를 효율적으로 탐색할 수 있습니다.

참고 문헌