[이진 탐색] 백준 1920번 수 찾기(Java)

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

1920번: 수 찾기

📚 문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

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

 

예제 입력	예제 출력
5 4 1 5 2 3 5 1 3 7 9 5	1 1 0 0 1

 

📝 문제 해결

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000) / 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다.
범위가 넓을 때 시간초과 없이 탐색하려면? 10만 * 10만의 시간복잡도를 가짐 > N이 10만개 이상이다?  > logN의 시간복잡도인 알고리즘 이진 탐색을 사용하자.

 

💻 코드

• 이진 탐색 메소드 구현

import java.util.*;

public class Main {

	static int N, M;
	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		int arr1[] = new int[N];
		for(int i=0; i<N; i++) arr1[i]=sc.nextInt();
		
		Arrays.sort(arr1);
		
		M = sc.nextInt();
		int arr2[] = new int[M];
		for(int i=0; i<M; i++) arr2[i]=sc.nextInt();
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<M; i++) sb.append(binarySearch(arr1,arr2[i])+"\n");
		System.out.println(sb);
	}
	
	public static int binarySearch(int[] arr, int target) {
		int start = 0;
		int end = N-1;
		int mid = 0;
		
		while(start <= end) {
			mid = (start+end)/2;
			if(arr[mid]==target) return 1;
			else if(arr[mid]>target) end = mid-1;
			else if(arr[mid]<target) start = mid+1;
				
		}
		return 0;
		
	}
}

 

• 자바에서 제공하는 이진 탐색 메소드

Arrays.binarySearch(a,b) : 배열 a에 b의 값이 존대한다면 해당 인덱스 반환
해당 값이 존재하지 않으면 음수 반환

import java.util.*;

public class Main {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int arr1[] = new int[N];
		for(int i=0; i<N; i++) arr1[i]=sc.nextInt();
		
		Arrays.sort(arr1);
		
		int M = sc.nextInt();
		int arr2[] = new int[M];
		for(int i=0; i<M; i++) arr2[i]=sc.nextInt();
		
		StringBuilder sb = new StringBuilder();
		
		for(int i=0; i<M; i++) {
			int index = Arrays.binarySearch(arr1, arr2[i]);
			if(index < 0) sb.append(0+"\n");
			else sb.append(1+"\n");
		}
		
		System.out.println(sb);
	}
}