19.11.25 (이분탐색에서 조건문은 항상!, boj1920 ,boj10816)

이분탐색에서 조건문은 항상 

lefT<=right 으로 해두자 right이 left보다 작아지는 경우가 존재하기 때문이다. 

 

#include 
#include 
#include 
using namespace std;

vector arr;
vector arr2;
//int arr[100000] = { 0 };
//int arr2[100000] = { 0 };

int binary_search(int x,int n) {
int left=0, right=n-1, pivot=(left+right)/2;
while (left <= right) {
if (x == arr[pivot]) return 1;
if (arr[pivot] > x) {
right = pivot - 1;
pivot = (left + right) / 2;
}
else if (arr[pivot] < x) {
left = pivot + 1;
pivot = (left + right) / 2;
}
}
return 0;
}

int main() {
int n,m,num;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d",&num);
arr.push_back(num);
}
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
scanf("%d", &num);
arr2.push_back(num);
}
sort(arr.begin(),arr.end());
for (int i = 0; i < m; i++) {
printf("%d\n", binary_search(arr2[i],n));
}
return 0;
}

 

boj1920 이다. 

 

 

 

 

어떤 수의 등장 횟수는 map을 이용하여 쉽게 해결할 수 있다. 

 

#include <cstdio>

#include <algorithm>

#include <map>

using namespace std;

map<int, int> mp;

int n, m, x;

int main() {

    scanf("%d", &n);

    for (int i = 0; i < n; i++) {

        scanf("%d", &x);

        mp[x]++;

    }

    scanf("%d", &m);

    for (int i = 0; i < m; i++) {

        scanf("%d", &x);

        printf("%d ", mp[x]);

    }

    return 0;

}

boj10816 이다. 시간초과 나왔다...

 

지난번에 배운 lower_bound와 upper_bound를 사용한다. (까먹어서 찾아봄.. ㅎㅎ; )

이 둘은 binary_search를 이용하기 때문에 이분탐색 쪽 파트에 들어가 있는 것 같다.