[백준 No.1920] 수 찾기 (이진 탐색)

문제 Rank
 - Silver 4 

---

문제

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을 출력한다.

---

문제핵심

- 검색 대상을 정렬 후 이진탐색한다면 정답이 바로 나옵니다. (Tip이랄께.. 없습니다.)
- 런타임 에러는 배열index를 벗어나지 않았나 확인 해봅시다. 
- 꼭 이진탐색을 사용하지 않아도 통과하는 문제이지만 이진탐색의 숙련도를 위해 이진탐색을 사용해보도록 합시다.

 

URL : www.acmicpc.net/problem/1920

1920번: 수 찾기

 

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();               //검색 대상 갯수
        int[] tcArray = new int[N];         //검색 배열

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

        Arrays.sort(tcArray);               //이진 탐색을 위한 오름차순 정렬

        int M = sc.nextInt();               //검색 값 갯수
        int[] checkArray = new int[M];      //검색 값 배열

        for (int i = 0; i < M; i++) {
            checkArray[i] = sc.nextInt();
        }

        for (int i = 0; i < M; i++) {
            int checkNum = checkArray[i];

            int left = 0;
            int right = N;
            boolean hasNum = false;
            while (left < right) {
                int mid = ((right - left) / 2 + left);

                if (checkNum == tcArray[mid]) {
                    hasNum = true;
                    break;
                } else if (checkNum < tcArray[mid]) { //찾는 숫자가 좌측에 있는경우
                    right = mid;
                } else { //우측에 있는 경우
                    left = mid + 1;
                }
            }

            System.out.println(hasNum ? 1 : 0);
        }
    }
}