[이진탐색] 백준 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안에 존재하는지 알아내면 된다. 

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

 

문제 분석

주어진 수들의 존재여부를 찾아야하므로, 탐색 알고리즘을 선택해야한다.
자연수의 범위가 100,000이므로 N^2 의 시간복잡도를 가지는 탐색알고리즘을 사용하면 안된다.
고로, 이진탐색을 사용하여 (O(logN)) 구현을 시도해보자 

• 이진탐색 조건
  • 정렬이 되어있어야함 ( 오름차순 or 내림차순 )

 

슈도코드

N(배열크기 저장)
arr (배열 저장)
arr.sort() (배열 정렬)

findNum (찾을 수)
for ( findNum 개수만큼 반복 ){
    int result = binarySearch(arr, findNum);
    // findNum이 있는지 여부 확인
    결과 출력 (있으면 1, 없으면 0)
}

binarySearch (arr, findNum) //구현
{
    low = 배열의 첫번째 위치
    high = 배열의 끝 위치
    middle 선언
    
    while( low <= high ) { // low 가 high보다 커지면 index를 벗어나므로 종료
        middle = (low + high) / 2; // low ~ high 사이의 중앙값 구하기
        
        if(arr[middle]값이 찾는값일경우){
            1 리턴
        }else if( findNum이 작을경우 ){
            왼쪽 데이터셋 설정
        }else{ //findNum이 클 경우
            오른쪽 데이터 셋 설정
        }
        
    }
    
    while문이 끝날경우, 찾는값이 없으므로 0 리턴
}

 

구현

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

public class App {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int arrSize = Integer.parseInt(bf.readLine());
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int[] arr= new int[arrSize];
        for (int i =0; i<arrSize; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        int findNumSize = Integer.parseInt(bf.readLine());
        st = new StringTokenizer(bf.readLine());
        for (int i =0; i< findNumSize; i++){
            int findNum = Integer.parseInt(st.nextToken());
            int result = binarySearch(arr, findNum);
            System.out.println(result);
        }
    }

    private static int binarySearch(int[] arr, int findNum){
        int low = 0;
        int high = arr.length -1;
        int middle = 0;
        while (low <= high) {
            middle = (low+high) / 2;            
            if(arr[middle] == findNum){
                return 1;
            }else if(arr[middle] > findNum){
                high = middle - 1;
            }else{
                low = middle + 1;
            }
        }
        return 0;
    }

}