[C++] 이분탐색

기본 로직:

정렬이 되어있는 상태에서 start 와 end 의 mid 를 이용하여 target 값 찾기

 

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int N = 8;
int M = 32;

vector<int> arr = {23,87,65,12,57,32,99,81};

int binarySearch(int target){
    int start = 0;
    int end = N-1;
    int mid;
    while (start <= end){
        mid = (start + end) / 2;
        if (arr[mid] == target){
            return mid;
        }
        else if (arr[mid] > target){
            // arr 중간 값이 target보다 크다면
            end = mid - 1; // 끝점을 옮긴다.
        }
        else{
            // arr 중간 값이 target보다 작다면
            start = mid + 1; // 시작점을 옮긴다.
        }
    }
    return mid;
}


int main(){
    sort(arr.begin(), arr.end());
    int answer = binarySearch(M);

    cout << answer << endl;

    return 0;
}

 

조금 더 생각해볼 문제: