BinarySearch 백준 알고리즘 1920 ‘수 찾기’ 문제풀이

Problem

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

Input
첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다.

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

Solution

시간 초과 문제를 해결하기 위해서는 단순 비교가 아닌 ‘이분탐색’이 필요하다.

Code

import java.util.Arrays;
import java.util.Scanner;
public class Main {
	public int solution(int[] arr, int num) {
		int high = arr.length-1, low = 0, mid = 0;
		
		while(low <= high) {
			mid = (high + low) / 2;
			
			if(arr[mid] == num)
				return 1;
			else if(arr[mid] > num)
				high = mid -1;
			else
				low = mid + 1;
		}
		
		return 0;
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int[] arr = new int[scan.nextInt()];
		
		for(int i = 0; i < arr.length; i++)
			arr[i] = scan.nextInt();
		Arrays.sort(arr);
		
		int m = scan.nextInt();
		for(int i = 0; i < m; i++)
			System.out.println(new Main().solution(arr, scan.nextInt()));
	}
}