[알고리즘] 벡준 1920 수 찾기 Java 문제풀이- Binary Search

수 찾기 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

308423

99118

65200

30.649%

문제

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

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

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

 

예제 입력 1 

5
4 1 5 2 3
5
1 3 7 9 5

 

예제 출력 1 

1
1
0
0
1

 

 

출 처

• 데이터를 추가한 사람: BaaaaaaaaaaarkingDog, djm03178, melthetensai
• 문제의 오타를 찾은 사람: bupjae
• 잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류

• 자료 구조
• 정렬
• 이분 탐색
• 해시를 사용한 집합과 맵

반응형

이번 문제의 풀이는 이진탐색 Binary Search Code로 푸는 방법이다. 

package test;

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

public class Solution{
	
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static int N;
	static int M;
	
	public static void main(String[] args) throws IOException{
		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);
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		
		for(int i =0; i < M; i++) {
			int ans =0;
			int X =Integer.parseInt(st.nextToken());
			int start =0;
			int end = arr.length -1;
			while(start <= end) {
				
				int middle = (start + end) /2;
				if(arr[middle] < X) {
					start = middle +1 ;
				}
				else if(arr[middle] >X) {
					end = middle -1;
				}
				else if(arr[middle] == X) {
					ans = 1;
					break;
				
			}
		
		}
		System.out.println(ans);
		}
	}
}