[ 탐색 ] 이진탐색(백준 1920)

 이진탐색(Binary Search)

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

• 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.
• 시간복잡도  O(logN)

💡  이진 탐색의 핵심 이론

 

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

 

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

 

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

 

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

☝🏻 이진 탐색을 사용하면 N개의 데이터에서 데이터를 반씩 줄여가며 탐색하기 때문에 총 log(N)번의 연산으로 원하는 데이터의 위치를 찾을 수 있다.

 

 1920 : 수 찾기

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

입력	출력
5 4 1 5 2 3 5 1 3 7 9 5	1 1 0 0 1

 

문제 풀이

• 2행에 나열된 숫자 배열에서 3행에 나열된 숫자 각각이 존재하는지 검사한다.
• 이진탐색을 통해 풀기!

 

실행 코드

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

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

        // 첫번째 배열 입력 받기 & 정렬
        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(A);

        int left; // 범위를 나타내기 위한 시작 값
        int right; // 범위를 나타내기 위한 마지막 값
        int mid; // 중앙값

        // 찾기
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            boolean exist = false; // 존재 여부를 검사
            left = 0; // 맨 처음 범위는 전체
            right = N-1; // 맨 처음 범위는 전체
            // 검사할 숫자들을 하나씩
            int x = Integer.parseInt(st.nextToken());
            // 실제 이진탐색 과정
            for(int j=0;left<=right;j++){
                mid = (left+right)/2; // 순회할때마다 중앙값을 업데이트
                if(x>A[mid]){ // 중앙값보다 오른쪽 범위일 때 범위를 중앙값보다 한칸 뒤부터 시작
                    left = mid+1;
                }else if(x<A[mid]){ // 중앙값보다 왼쪽 범위일 때 범위를 중앙값보다 한칸 앞을 마지막으로
                    right = mid-1;
                }else{ // 타깃을 찾았을 때 boolean값을 true처리하고 반복문 종료
                    exist = true;
                    break;
                }
            }
            if(exist)
                System.out.println("1");
            else
                System.out.println("0");
        }
    }
}

 

한번풀엇던거라쉽네ㅋㅋElZl~