5주차 : 이진탐색 문제1

✔ BOJ_10815

풀이 과정

첫 번째 시도는 이진 탐색 개념을 기반으로 binarySearch를 하는 함수를 직접 만들어서, middle 인덱스를 구한 후, 배열의 middleindex 값보다 target값이 크면 그 이상의 배열을, 작으면 그 이하의 배열을 Arrays.copyOfRange() 반환하여 재귀호출하는 식으로 코드를 구현했는데, 쓸데없이 copyOfRange를 한 탓인지 시간초과가 나왔다 ㅠ

package BaekJoon.Binary;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_10815_adv {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int n,m;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        StringTokenizer st= new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        m = Integer.parseInt(br.readLine());
        st= new StringTokenizer(br.readLine());

        for(int i=0;i<m;i++){
            int num = Integer.parseInt(st.nextToken());
            // 이진탐색을 해서 해당 숫자가 있는 경우
            if(binarySearch(num)) bw.write("1 ");
            else bw.write("0 ");
        }
        bw.close();
        br.close();
    }
    private static boolean binarySearch(int num){
        int leftIndex = 0;
        int rightIndex= n-1;

        while(leftIndex <= rightIndex){
            int middleIndex = (leftIndex + rightIndex)/2;
            int mid = arr[middleIndex];

            if(num<mid) rightIndex = middleIndex-1;
            else if(num>mid) leftIndex = middleIndex+1;
            else return true;
        }
        return false;
    }
}

근데 고칠 힘은 또 없어서 이진 탐색 백준 풀이는 처음이니까~.. 하는 맘으로 참고 코드를 찾아봤다. 참조 블로그 해당 코드를 보면서 배운 점은, 굳이 arr를 받아서 copyOfRange로 새로 만들 필요가 없고 재귀함수로 풀 필요도 없구나..였다💧 전역 변수로 arr를 선언하고, right 및 left index 변수를 선언하여 while문을 이용하면 깔끔하게 해결되는 것을 확인할 수 있었기 때문이다.