자바 | 백준 | 1920 | 수 찾기

Solution 이분탐색

N의 값 큼 -> 이분 탐색

 

package BOJ;

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

public class BOJ_1920 {

	static int N, M;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		N = Integer.parseInt(br.readLine());
		int[] 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 temp = Integer.parseInt(st.nextToken());
			if (search(temp, A))
				sb.append("1").append("\n");
			else
				sb.append("0").append("\n");
		}
		System.out.println(sb);
	}

	static boolean search(int x, int[] arr) {
		int start = 0;
		int end = arr.length - 1;
		
		while (start <= end) {	// = 없으면 하나 비교 못 함..
			int mid = (start + end) / 2;

			if (arr[mid] == x) return true;
			else if (arr[mid] < x) start = mid + 1;
			else end = mid - 1;
		}
		return false;
	}

}

 

www.acmicpc.net/problem/1920

1920번: 수 찾기