이진 탐색(binary search)

이진 탐색

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

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

 

* 시간복잡도 : O(logN)

 

 

이진 탐색 과정

예) 타겟 데이터 : 55, 총 데이터 개수 : 16, 데이터는 오름차순 정렬되어 있는 상태

 

1. 현재 데이터의 중앙값을 선택한다.

ex) 41을 중앙값으로 선택

 

2. 중앙값 > 타깃 데이터일 때 중앙값을 기준으로 왼쪽 데이터셋 선택

 

3. 중앙값 < 타깃 데이터일 때 중앙값을 기준으로 오른쪽 데이터셋 선택

ex) 55가 41보다 크므로 오른쪽 데이터셋을 선택

ex) 중앙값 선택 : 67 ... 반복

 

4. 1~3번을 반복하다가 중앙값 == 타깃 데이터일 때 탐색 종료

---

백준 온라인저지 1920번

import java.util.Arrays;
import java.util.Scanner;

public class P1920_원하는정수찾기 {

    public static void main(String[] args) {
        // N의 범위가 100,000이므로 반복문으로는 문제를 풀 수 없음
        // 이진탐색을 사용해 해결

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] A = new int[N];
        for(int i=0; i<N; i++) {
            A[i] = sc.nextInt();
        }

        Arrays.sort(A);

        int M = sc.nextInt();
        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 midIdx = (start + end) / 2;
                int midValue = A[midIdx];

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

            if(find) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }

        }

    }
}

 

---

백준 온라인저지 10815번

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

public class P10815_숫자카드 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

        Arrays.sort(arr);
        for(int i=0; i<M; i++) {
            boolean find = false;
            int target = arr2[i];

            int start = 0;
            int end = N-1;
            while(start <= end) {
                int midIdx = (start + end) / 2;
                int midValue = arr[midIdx];

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

            if(find) {
                System.out.print(1 + " ");
            } else {
                System.out.print(0 + " ");
            }
        }
    }
}