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

✅ 문제

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

✅ 분류

이분탐색

✅ 공부한 내용

N의 최대범위가 10만이므로, 단순 반복문으로는 풀 수 없다.

이분탐색을 적용하면 O(nlogn) 시간 복잡도로 해결할 수 있다.

 

이분 탐색은 데이터가 정렬되어있는 상태에서 원하는 값을 찾아내는 알고리즘이다.

대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.

[이진 탐색 과정] - 오름차순으로 정렬된 데이터인 경우 (내림차순이면 조건 반대)

1. 현재 데이터셋의 중앙값을 선택한다
2. 중앙값 > 타깃데이터일때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.
3. 중앙값 < 타깃 데이터일 때, 중앙값 기준으로 오른쪽 데이터셋을 선택한다.
4. 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다.

✅ 풀이

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

// 이분탐색
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder(); // 🔥 결과를 저장할 StringBuilder
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        StringTokenizer 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++) {
            boolean find = false;
            int target = Integer.parseInt(st.nextToken());

            // 이진탐색 시작
            int start = 0;
            int end = arr.length - 1;

            while (start <= end) {
                int mid_index = (start + end) / 2;
                int mid_value = arr[mid_index]; // 중앙값

                if (mid_value > target) {
                    end = mid_index - 1;
                } else if (mid_value < target) {
                    start = mid_index + 1;
                } else {
                    find = true;
                    break;
                }
            }

            // 결과 저장
            sb.append(find ? "1\n" : "0\n");
        }
        System.out.print(sb); // 🔥 한 번에 출력
    }
}