[1920번] 수 찾기 ( 이진탐색 )

이 문제는 이중 반복문으로 풀 경우, 최악일 때 100,000*100,000으로 1억을 넘어간다.
따라서, 완전 탐색으로는 풀 수 없으므로 이진 탐색으로 풀자.
log(100,000) 은 100을 넘어가지 않으므로 1초안에 풀 수 있다.
전제인 정렬해주는 Array.sort()도 대강 O(nlogn)의 시간복잡도가 나온다.
총 시간 복잡도는 nlogn+nlogn = 2nlogn -> nlogn

✅ 이진 탐색 (binary search)

[전제 조건]
데이터가 정렬되어 있는 상태

중앙 값과 찾고자 하는 값을 비교해 데이터 크기를 절반 씩 줄이면서 찾아내는 알고리즘

시간 복잡도 : O(logN)
예) 16개의 데이터면 최대 4번으로 원하는 데이터의 위치를 찾을 수 있다.

손으로 따라가보자.

✅ 코드

시작과 끝을 i, j 로 두지 말고 start, end 로 두자.

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

public class Main {

	static int arr[];

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

		int n = Integer.parseInt(br.readLine());
		arr = new int[n];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr);

		int m = Integer.parseInt(br.readLine());

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < m; i++) {
			int num = Integer.parseInt(st.nextToken());
			System.out.println(findNumber(num));
		}

	}

	static private int findNumber(int num) {

		boolean find = false;
		int result;
		int start = 0;
		int end = arr.length - 1;

		while (start <= end) { //탐색할 부분이 없을 때까지 탐색
			int middle = (start + end) / 2;
			int middleValue = arr[middle];
			if (middleValue > num) {
				end = middle - 1;
			} else if (middleValue < num) {
				start = middle + 1;
			} else {
				find = true;
				break;
			}
		}

		if (find) {
			result = 1;
		} else {
			result = 0;
		}

		return result;
	}
}