백준 1920번
https://www.acmicpc.net/problem/1920

---

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

---

생각하기

수를 찾는 방법을 생각을 했을 때, 이분탐색을 사용하는게 맞는 거 같아서
정리를 한번 해보기로 했다.

이분탐색은 이전에 '랜선자르기' 문제에서 한번 해봤던 경험이 있으니까 제대로
문제 이해만 한다면 적용하는건 쉽다고 생각했는데..

문제를 풀다보니 뭐가 자꾸 마음대로 안풀린다..

이전 '랜선자르기'에서는 수가 정렬되어 있고, 순차적으로 증가되는 숫자였던 반면에
여기서 Nlist와 Mlist는 단순히 크기만 정해져있고 결국 원하는 숫자를 찾기위해서는
list의 인덱스 값과 인덱스에 해당하는 값까지 2가지가 필요했다.

그래서 halfidx, max_idx, min_idx 로 3가지 인덱스를 찾아줄 변수를 만들고

그리고 우리가 찾을 값은 어차피 이분탐색을 통해 중앙에 해당하는 값으로 찾을 거기 때문에 value에 해당하는 변수는 Nlist_halfValue 하나만 만들어주면 된다.

결국 이 문제의 핵심은 index를 이분탐색하라는 의미!

---

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		List<Long> Nlist = new ArrayList<>();
		List<Long> Mlist = new ArrayList<>();
		List<Integer> result = new ArrayList<>();
		
		int N = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			Nlist.add(Long.parseLong(st.nextToken()));
		}

		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<M; i++) {
			Mlist.add(Long.parseLong(st.nextToken()));
		}

		Collections.sort(Nlist);
		int Nlist_length = N-1;

		for(long Mnum : Mlist) {
			int halfidx = Nlist_length/2;
			int max_idx = Nlist_length;
			int min_idx = 0;

			long Nlist_halfValue = 0;

			while(max_idx >= min_idx) {
				halfidx = (max_idx + min_idx)/2;
				Nlist_halfValue = Nlist.get(halfidx);
				if(Mnum > Nlist_halfValue) {
					min_idx = halfidx + 1;
				}
				else {
					max_idx = halfidx - 1;
				}

				if(Nlist_halfValue == Mnum) {
					break;
				}
			}

			if(Nlist_halfValue == Mnum) {
				result.add(1);
			}
			else {
				result.add(0);
			}
		}	

		int length = result.size();
		for(int i=0; i<length; i++) {
			System.out.println(result.get(i));
		}
	}
}