바이너리 서치( Binary Search )란?

• Binary Search란 이진 탐색 트리에서 원하는 자료를 찾는 방식과 동일한 방식으로 오름 차순으로 정렬된 배열에서 원하는 원소를 찾는 방법을 말하며 시간 복잡도는 O(logN) 입니다.

Binary Search 코드

#include <iostream>
#include <vector>

int BinarySearch(int findVal, const std::vector<int>& arr)
{
    int low = 0;
    int high = arr.size() - 1;

    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (arr[mid] < findVal)
        {
            low = mid + 1;
        }
        else if(arr[mid] > findVal)  {
            high = mid - 1;
        }
        else {
            return mid;
        }
    }

    return -1;
}

int main()
{
    std::vector<int> v = { 1,3,5,6,7,9,11 };

    std::cout << BinarySearch(3, v);

    return 0;
}

• low와 high의 중간값과 찾고자하는 값과의 대소 비교를 후 low 또는 high를 다시 셋팅하여 탐색 범위를 좁혀 나아가고 이러한 방식을 반복하여 원하는 원소를 찾아냅니다.