이진 검색 알고리즘은 정렬된 배열에서 값을 찾는 효율적인 방법으로, 배열의 중간 값과 비교하여 원하는 값을 찾는 방식입니다.

알고리즘 설명

1. 먼저 배열을 정렬합니다.
2. 배열의 중앙에 위치한 값과 찾으려는 값을 비교합니다.
3. 만약 배열의 중앙 값이 찾으려는 값과 같다면 원하는 값을 찾은 것이므로 알고리즘을 종료합니다.
4. 만약 배열의 중앙 값이 찾으려는 값보다 크다면, 왼쪽 반 배열에서 다시 이진 검색을 수행합니다.
5. 만약 배열의 중앙 값이 찾으려는 값보다 작다면, 오른쪽 반 배열에서 다시 이진 검색을 수행합니다.
6. 원하는 값을 찾거나 검색할 범위가 없어질 때까지 2단계로 돌아가 반복합니다.

예제 코드

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

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

시간 복잡도

이진 검색 알고리즘의 시간 복잡도는 O(logN)으로 매우 효율적입니다.

요약

이진 검색 알고리즘은 정렬된 배열에서 값을 찾는 데에 사용되며, 평균적으로 O(logN)의 시간 복잡도를 가집니다. 이러한 특성으로 인해 많은 경우에 효율적으로 사용됩니다.

참고 자료

• GeeksforGeeks - Binary Search
• Wikipedia - Binary Search Algorithm