BOJ::1920 수 찾기

https://www.acmicpc.net/problem/1920


이분탐색 문제이다.

A배열을 정렬 시킨 후 하나씩 이분탐색 하면 된다.


<JAVA>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    
    static int n,m;
    static int a[];
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String args[]) throws NumberFormatException, IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        a=new int[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i =0 ; i < n ; i++){
            a[i]=Integer.parseInt(st.nextToken());
        }
        Arrays.sort(a);
        
        m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < m ; i ++){
            int x=Integer.parseInt(st.nextToken());
            
            int low = 0;
            int high = n-1;
            int mid;
            
            while(true){
                if(low > high){
                    sb.append("0\n");
                    break;
                }
                mid = (low+high)/2;
                if(a[mid]==x){
                    sb.append("1\n");
                    break;
                }
                else if(a[mid] < x){
                    low = mid+1;
                }
                else{
                    high=mid-1;
                }
            }
        }
        System.out.println(sb.toString());
    }
}
 
cs



C++


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
int n, m;
int a[100001];
string res;
 
int main() {
    res = "";
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
 
    sort(a,a+n);
 
    cin >> m;
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
 
        int low = 0;
        int high = n - 1;
        int mid;
 
        while (true) {
            if (low > high) {
                res += "0\n";
                break;
            }
 
            mid = (low + high) / 2;
            if (x == a[mid]) {
                res += "1\n";
                break;
            }
            else if (x > a[mid]) {
                low = mid + 1;
            }
            else {
                high = mid - 1;
            }
        }
    }
    cout << res;
}
cs


저작자표시

'BOJ::문제풀이' 카테고리의 다른 글

1932 숫자삼각형  (0) 2018.01.01
1929 소수 구하기  (0) 2018.01.01
1890 점프  (0) 2017.12.31
1874 스택 수열  (0) 2017.12.31
1759 암호 만들기  (0) 2017.12.31

+ Recent posts

티스토리툴바