[BAEKJOON] - 1920번 : 수 찾기

1920번 문제 링크

이분탐색

데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘입니다. 대상 데이터의 중간값과 찾고자 하는 값을 비교하여 데이터의 크기를 절반씩 줄이면서 대상을 찾습니다.

이분 탐색 문제의 경우, 실제 살짝만 꼬아도 너무 어렵기 때문에 당장에는 기본적인 로직을 구현할 정도만 익혀둔 뒤 추후 활용문제들을 집중적으로 풀어 익숙해져야 합니다.

• 시간 복잡도 : O(logN)

핵심이론
1. 오름차순 정렬
2. 중앙값 > 타깃 데이터인 경우, 중앙값 기준 왼쪽 데이터셋을 선택
3. 중앙값 < 타깃 데이터인 경우, 중앙값 기준 오른쪽 데이터셋을 선택
4. 1~3 과정을 반복하다가 중앙값 == 타깃 데이터일 때 탐색 종료

⏲️ 시간 복잡도

• 제한 시간 2초에 제한 갯수가 100,000 개이므로, 이는 O(NlogN) 이하의 알고리즘을 사용해야 합니다.

📜 로직

• N 개의 데이터들을 배열에 담아 정렬해줍니다.
• M 개의 찾아야 할 숫자들을 반복문을 통해 이분 탐색을 수행합니다.
• 이분 탐색 시, N개의 데이터의 중간값을 타겟과 비교하여 타겟이 작은 경우 중간값을 제외한 왼쪽 그룹으로 타겟이 큰 경우 중간값을 제외한 오른쪽 그룹으로 탐색 범위를 좁혀갑니다.
• 타겟과 같은 값이 있는 경우 탐색을 종료한 뒤 1을 출력 아닌 경우 0을 출력합니다.

😀 성공

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

public class Main{
    static int[] a;
    static int n;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        
        a = new int[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for(int i=0; i < n; i++){
            a[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(a);
        
        int m = Integer.parseInt(br.readLine());
        
        st = new StringTokenizer(br.readLine());
        
        br.close();
        
        StringBuilder sb = new StringBuilder();
        
        for(int i=0; i<m; i++){
            int target = Integer.parseInt(st.nextToken());
            
            if(binarySearch(target)){
                sb.append(1).append("\n");
            }
            else{
                sb.append(0).append("\n");
            }
            
        }
        
        System.out.println(sb);
    }
    
    static boolean binarySearch(int target){
        int start = 0;
        int end = n-1;

        while(start <= end){

            int half = (start + end) / 2;

            if(a[half] > target){
                end = half-1;
            }
            else if(a[half] < target){
                start = half+1;
            }
            else{
                return true;
            }
        }
        return false;
    }
}