[BOJ] 1920. 수 찾기

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

1920번: 수 찾기

---

접근 방법

전형적인 정렬 및 탐색 문제이다. 이분 탐색을 이용했다.

중간 지점에 구하고자 하는 값이 위치할 때까지 중간 지점을 기준으로 반씩 분할하며 각각 탐색을 진행한다.

 

소스 코드

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

public class Main {
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int[] n;
static int[] m;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.valueOf(br.readLine());
		n = new int[N];
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<N; i++) {
			n[i] = Integer.valueOf(st.nextToken());
		}
		
		int M = Integer.valueOf(br.readLine());
		m = new int[M];
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<M; i++) {
			m[i] = Integer.valueOf(st.nextToken());
		}
		
		Arrays.sort(n);
		 
		for(int i=0; i<M; i++) {
			bi_search(0, n.length-1, m[i]);
		}
		System.out.println(sb.toString());
	}
	
	static void bi_search(int start, int end, int t) {
		int mid = (start + end) / 2;
		
		if (end < start) {
			sb.append("0 ");
			return;
		}
		if (n[mid] == t) {
			sb.append("1 ");
			return;
		}
		else if (n[mid] > t) {
			bi_search(start, mid-1, t);
		}
		else {
			bi_search(mid+1, end, t);
		}
	}
}