Binary_Search

bool binary_search(ForwardIterator first, ForwardIterator last, const T& value);

Binary_Search는 이진 탐색 알고리즘을 사용한다.

• 데이터가 정렬되어 있어야 사용 가능하다.
• 탐색 범위를 반씩 나누어 찾고자 하는 값이 포함된 범위를 좁혀나간다.
• <algorithm> 헤더에 정의되어있다.

내부적인 구조를 간략하게 살펴보면

bool solution(int TargetNum) 
{
    int Start = 1;
    int End = 10;
    int Mid;

    while (Start <= End)
    {
        Mid = (Start + End) / 2;

        if (Mid == TargetNum) return true;

        if (Mid < TargetNum) Start = Mid + 1;
        if (Mid > TargetNum) End = Mid - 1;
    }
}

int main() 
{
    bool Answer = solution(7);

	return 0;
}

 이렇게 모든 범위를 선형적으로 다 탐색하지 않고, 범위를 줄여나가며 찾는 이진 탐색 기법을 활용함을 볼 수 있다.

탐색 범위를 절반씩 줄이기 때문에 데이터의 크기가 커져도 비교 횟수는 로그 스케일로 증가해 O(log n)의 시간 복잡도를 가지고, 만약 정렬을 해야한다면 추가적인 시간 복잡도 O(n log n)가 발생한다. 

탐색이 여러 번 수행되거나, 정렬된 데이터가 이미 주어진 경우라면 binary_search가 효율적이다.