119.水を探す


白駿

1. Python


def binary_search(array, target, start, end):
  if start > end:
    return None
  
  mid = (start + end) // 2

  if array[mid] == target:
    return mid

  elif array[mid] > target:
    return binary_search(array, target, start, mid - 1)
  
  else:
    return binary_search(array, target, mid + 1, end)


n = int(input())
array = list(map(int, input().split()))
array.sort()

m = int(input())
find = list(map(int, input().split()))

for i in range(m):
  r = binary_search(array, find[i], 0, n-1)
  
  if r == None:
    print(0)
  else:
    print(1)
    


2. Java



import java.io.*;
import java.util.*;

public class Main {
    private static int N;
    private static int M;
    private static int[] A;
    private static int[] Q;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        A = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        Q = new int[M];

        st = new StringTokenizer(br.readLine());
        for (int i = 0 ; i < M ; i++) {
            Q[i] = Integer.parseInt(st.nextToken());
        }

        // sorting
        Arrays.sort(A);
        // cpp
        // #include <algorithm>
        // sort(a, a + n);

        // binary search
        for (int i = 0 ; i < M ; i++) {
            System.out.println(binary_search(Q[i]));
        }
    }

    // 있으면 1
    // 없으면 0
    public static int binary_search(int key) {
        int left, right, mid;
        left = 0;
        right = N - 1;
        while (left <= right) {
            mid = (left + right) / 2;
            if (A[mid] == key) {
                return 1;
            }
            else if (key < A[mid]) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return 0;
    }
}