[백준/java] 1920: 수 찾기 - 이분 탐색

728x90

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

1920번: 수 찾기

 

백준 1920 수 찾기

 

이번 문제는 이분 탐색을 이용해서 풀어야한다.

 

먼저 lt와 rt를 사용해서 중간을 구해야하는데, m 배열과 비교할 때 N의 배열과 비교할 것이므로

끝점의 기준을 N-1으로 한다.

int lt = 0;
int rt = n - 1;

 

0부터 n-1까지 기준을 잡으면 된다.

 

반응형

 

이분탐색은 lt의 위치가  rt의 위치보다 커지면 탐색이 종료가 된다.

 

mid의 위치를 구해서, arrN[mid] 값이 배열 m의 값보다 작으면 rt의 위치를 mid -1로 해주고,

 

배열 m의 값보다 크면 lt의 위치를 mid + 1로 해준다.

 

값이 같으면 탐색을 종료한다.

 

package binarySearch;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 
 * https://www.acmicpc.net/problem/1920
 * 백준 1920번 수 찾기(이분탐색)
 */

public class P1920_FindNumber {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int[] arrN = new int[n];
		for (int i = 0; i < n; i++) {
			arrN[i] = sc.nextInt();
		}
		Arrays.sort(arrN);
		
		int m = sc.nextInt();
		int[] arrM = new int[m];
		for (int i = 0; i < m; i++) {
			arrM[i] = sc.nextInt();
		}
		
		for(int k : arrM) {
			int lt = 0;
			int rt = n - 1;
			
			boolean find = false;
			
			while(lt <= rt) {
				int mid = (lt + rt) / 2;
				if(k == arrN[mid]) {
					System.out.println(1);
					find = true;
					break;
				} else if(k > arrN[mid]) {
					lt = mid + 1;
				} else rt = mid - 1;
			}
			
			if(!find) System.out.println(0);
		}
	}
}