분할정복 알고리즘

분할된 작은문제는 원래문제와 성격이 동일하다 -> 입력크기만 작아짐
분할된 문제는 서로 독립적이다

1. 병합정렬
   하나의 리스트를 두 개의 균등한 크기로 분할

2. 퀵정렬
   피벗을 기준으로 주어진 배열을 두 부분 배열로 분할하고 각 부분 배열에 대해 퀵 정렬을 순환적으로 적용

3. 이진탐색
   정렬된 데이터를 효과적으로 탐색할 수 있는 방법
   기준보다 작으면 좌측 탐색 크면 우측 탐색

문제

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

내풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class B1920 {
	static int n;
	static int[] arr1;
	static int[] arr2;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		arr1 = new int[n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			
			arr1[i]=Integer.parseInt(st.nextToken());
		}
		
		st = new StringTokenizer(br.readLine());
		int m =Integer.parseInt(st.nextToken());
		
		Arrays.sort(arr1);
		arr2 = new int[m];
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < m; i++) {
			
			arr2[i]=Integer.parseInt(st.nextToken());
		}
		
		for (int i = 0; i < m; i++) {
			search(arr2[i]);	
		}
	}
	
	private static void search(int target) {
		int pl =0;
		int pr =arr1.length-1;
		boolean find =false;
		
		while(pl<=pr) {
			int pc = (pl+pr)/2;
			
			
			if(arr1[pc]>target) {
				pr = pc-1;
			}
			else if(arr1[pc]<target) {
				pl = pc+1;
				
			}
			else {
				find =true;
				break;
			}	
		}
		
		if(find) {
			System.out.println(1);
		}
		else {
			System.out.println(0);
		}
	}

}