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

문제

 

풀이

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

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
		int[] src = new int[n];
		for (int i = 0; i < n; i++) {
			src[i] = scanner.nextInt();
		}
		
		int m = scanner.nextInt();
		int[] target = new int[m];
		for (int i = 0; i < m; i++) {
			target[i] = scanner.nextInt();
		}
		
		scanner.close();
		Arrays.sort(src);
		
		outer: for (int i = 0; i < m; i++) {
			int min = 0;
			int max = n - 1;
			int t = target[i];
			while (min <= max) {
				int mid = (min + max) / 2;
				
				if (src[mid] == t) {
					System.out.println(1);
					continue outer;
				} else if (src[mid] > t) {
					max = mid - 1;
				} else {
					min = mid + 1;
				}
			}
			System.out.println(0);
		}
	}
	
}

• src array를 정렬한다.
• idx의 min, max를 0, 배열 마지막 idx로 설정한 후, mid값을 min ~ max의 중간값으로 설정한다.
• min > max보다 커지는 시점까지 반복한다.
• 찾으려는 대상 t가 src[mid]보다 크면 min을 중간값 + 1로 설정, 작으면 max를 중간값 - 1로 설정함으로써 반씩 범위를 줄여나간다.

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