[이진 탐색] 백준 1920

 

 

이진 탐색은 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘으로 시간 복잡도는 nlogn이다.

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

 

 

탐색 방법

1. 데이터에서 중앙값(median)을 선택한다.

2. 중앙값>타깃 데이터 라면, 중앙값을 기준으로 왼쪽 데이터셋을 선택한다.

3. 반대인 경우라면 오른쪽 데이터셋을 선택한다.

4. 1~3을 반복하면서 중앙값 == 타깃 데이터를 찾는다.

 

내가 찾고자 하는 데이터 = 55

3 7 13 15 23 35 38 41 46 49 55 57 68 72 77 68  -> 오름차순으로 배열 되어있는 상태, 중앙값을 41로 설정

41과 55 비교 -> 55가 더 크므로 오른쪽 데이터 셋 선택

46 49 55 57 68 72 77 68   -> 오름차순으로 배열 되어있는 상태, 중앙값을 57로 설정

57과 55 비교 -> 57이 더 크므로 왼쪽 데이터 셋 선택

46 49 55

....

55찾기!

 

만약 중앙 값을 특정 두개의 인덱스의 가운데 값으로 커스텀한 경우, 소수점이 나올 때는 버려준다

예를 들어 1과 2의 중앙값은 1.5인데 이때는 소수점을 버려 1을 중앙값으로 설정한다.

 

백준 1920번 문제에 적용해보겠다!

오름차순으로 정렬을 한 후 이진 탐색을 진행해야 하므로 시간이 더 오래 걸리는 것은 아닌가? 하는 생각이 들 수도 있지만, 정렬하는 데 nlogn, 이진 탐색 시 nlogn으로 총 2nlogn(시간 복잡도 계산에서 앞의 상수는 무시해도 됨)이라는 괜찮은 시간 복잡도를 갖고 있다.

 

public class 원하는_정수찾기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a[] = new int[n];
        for(int i =0;i<n;i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(a);
        int m = Integer.parseInt(br.readLine());
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i<m; i++) {
            boolean find = false;
            int target = sc.nextInt();
            int start = 0;
            int end = a.length-1;
            while (start <= end){
                int mid_index = (start + end)/2;
                int mid_value = a[mid_index];
                if(mid_value>target) {
                    end = mid_index-1;
                } else if (mid_value<target) {
                    start=mid_index+1;
                } else {
                    find = true;
                    break;
                }
            }
            if (find)System.out.println(1);
            else System.out.println(0);
        }

    }
}