이분탐색 Binary Search

이분탐색은 두 부분으로 찾을때까지 분할하면서 찾는 탐색알고리즘 입니다. 

선형탐색보다 압도적으로 속도가 빠르지만 정렬된 알고리즘에 한해서 사용할수 있다는 제약이 있습니다. 

 

변수 3개(start, end, mid)를 사용하여 탐색합니다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정입니다. 

 

int binary_search(vector<int> arr, int target) {
    sort(arr.begin(), arr.end());

    int left = 0;
    int right = arr.size() - 1;

    int mid = 0;
    while(left <= right){
        mid = (left + right)/2;
        if(target == arr[mid])return mid;
        else if(target < arr[mid])right = mid - 1;
        else if(target > arr[mid])left = mid + 1;
    }
    return arr.size();
}