수 찾기

1920번 : 수 찾기

알고리즘

• 처음에는 이중 반복문을 이용해서 푸는 바람에 시간초과가 발생했음.

• 다른 방법을 찾아보다가 이분탐색을 사용하게 됨.

• 이분 탐색은 쉽게 말하자면 두 부분으로 쪼개면서 탐색하겠다는 것이다.

• 1부터 n 까지의 수를 전부 탐색하는 것이 아니라 mid (중간 값)을 구하고, key값이 중간 값과 일치하는지, 중간 값보다 작은지 아니면 더 큰지를 비교하여 크거나 작다면 다시 이등분 이등분 반복하여 key 값을 찾아나가는 방법을 말한다.

• up & down 게임을 떠올리면 쉬움.

출처

---

코드

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

public class Find_Number_1 {
    public static void main(String[] args) {


        //백준 1920번 자바

        Scanner sc = new Scanner(System.in);


        int N = sc.nextInt();

        int arr1 [] = new int[N];

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

        Arrays.sort(arr1); //이분탐색을 이용하기 때문에 반드시 정렬되어 있어야 함

        int M = sc.nextInt();

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i<M; i++){

            if (binarySearch(arr1,sc.nextInt()) >= 0){
                sb.append(1).append('\n');
            }
            else {
                sb.append(0).append('\n');
            }

        }
        System.out.println(sb);





    }

    public static int binarySearch(int[] arr1, int key) {

        int low = 0;
        int high = arr1.length -1;

        while(low <= high){

            int mid = (low+high) / 2 ;

            if (key < arr1[mid]){
                high = mid-1;
            } else if (key > arr1[mid]) {
                low = mid+1;

            }
            else{
                return mid;
            }

        }



        return -1;
    }
}

• 이분탐색을 위해선 모든 수가 오름차순으로 정렬되어 있다는 가정이 필요하기 때문에 Arrays.sort() 를 사용하였다.