[c++][algorithm][baekjoon]1920 수 찾기

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

예제 입력 1 
5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1 
1
1
0
0
1

풀이

-오름차순 정렬

1 2 3 4 5

-숫자 1개씩 이진 탐색으로 검색 

중간 값을 구하기 위한 s,e값은 A[] array의 순서이다. 

if s = 0, e = N-1, d=1 부터 시작하면 

m = (s + e)/2; 

m = (0 + 4)/2=2;

A[2] =3이므로 

if(A[m] >d) 이므로 e=m-1로 값을 변경후 다시 찾는다.

s=0, e=1로 값 설정

 

m=(0+1)/2=0;

if(A[0]==d)에 부합하므로 값을 찾아서 return 1을 전달해 준다. 

/*[1920]수찾기*/
#include <bits/stdc++.h>
using namespace std;
#define MAXN ((int)1e6)
int N;
int A[MAXN +10];
int M;
int X[MAXN+10];

void InputData(){
    cin >> N;
    for(int i =0; i<N; i++){
        cin >> A[i];
    }
    cin >> M;
    for(int i=0; i<M; i++){
        cin >> X[i];
    }
}
bool BinarySearch(int s, int e, int d){
    int m;
    while(s<=e){
        m=(s+e)/2;
        if(A[m]==d) return 1;
        else if(A[m]>d) e=m-1;
        else s = m+1;
    }
    return 0;
}
void Solve(){
    sort(A,A+N);
    for(int i=0; i<M; i++){
        printf("%d\n", BinarySearch(0, N-1, X[i]));
    }
}
int main(){
    InputData();
    Solve();
    return 0;
}
/*[1920]수찾기*/

 

libray를 이용해서 풀이하면 아래와 같이 간단히 할 수 있다.

 

http://www.cplusplus.com/reference/algorithm/binary_search/

#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN ((int)1e6+10)
int N,M;
int A[MAXN],X[MAXN];
void Solve(){
    sort(A,A+N);
    for(int i=0; i<M; i++)
        cout<<binary_search(A, A+N, X[i])<<"\n";
}
void InputData(){
    cin >> N;
    for(int i =0; i<N; i++)
        cin >> A[i];
    cin >> M;
    for(int i=0; i<M; i++)
        cin >> X[i];
}
int main(){
    InputData();
    Solve();
    return 0;
}