[백준 JAVA] 1920번: 수 찾기

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

 

1. binarySearch를 사용한 방법

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

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

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

		Arrays.sort(arr);

		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			int cur = Integer.parseInt(st.nextToken());
			if (Arrays.binarySearch(arr, cur) >= 0) {
				System.out.println(1);
			} else {
				System.out.println(0);
			}
		}
	}
}

 

 

 

2. 이진탐색 직접 구현

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

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

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

		Arrays.sort(arr);
		
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			int cur = Integer.parseInt(st.nextToken());
			System.out.println(bs(arr, cur));
		}
	}
	
	public static int bs(int[] arr, int key) {
		int lo = 0;
		int hi = arr.length -1;
		while(lo <= hi) {
			int mid = (lo+hi) / 2;
			if(key < arr[mid]) {
				hi = mid-1;
				
			}else if(key > arr[mid]) {
				lo = mid + 1;
			} else {
				return 1;
			}
		}
		
		return 0;
	}
}