(C++) ★Binary Search Intermediate I - 1 Solved★

★ 1920 수 찾기 ★

//1920
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
using namespace std;

int binary_search(vector<int> &arr, int target){
    int start, end;
    start = 0;
    end = arr.size()-1;
    int mid;
    while(start<=end){
        mid = (start+end)/2;
        if(target<arr[mid]){
            end = mid - 1;
        }
        else if(arr[mid]<target){
            start = mid + 1;
        }
        else{
            return 1;
        }
    }
    return 0;


}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M, x, y;
    cin >> N;
    vector<int> arr1(N);
    for(int i=0;i<N;i++){
        cin >> x;
        arr1[i]=x;
    }

    cin >> M;
    vector<int> arr2(M);
    for(int i=0;i<M;i++){
        cin >> y;
        arr2[i]=y;
    }
    sort(arr1.begin(), arr1.end());

    for(int i:arr2){
        cout << binary_search(arr1,i) << '\n';
    }

	return 0;
}

 

👩🏼‍🔬 이분탐색 코드 주의점)

(1) while(start < end)가 아니라 while(start<=end)

(2) TLE 날 경우 vector array 자체의 parameter 복사에 시간 초과 날 수 있으므로 & 기호 붙여서 주소를 parameter로 복사해 시간 초과 해결

 

👩🏼‍🔬 추가로 vector<int> arr1(N)과 같이 일단 vector array 내의 원소 개수 N개 또는 M개 이렇게 초기화 할 수 있다.

---