<Algorithm> 57. 10815번 숫자카드(BinarySearch)

1. 10815번 숫자카드

• 기본 이진탐색 문제, 이진탐색은 임의의 중간지점을 선택하고 찾고자 하는 값과 대소비교하여 반복적으로 찾는 알고리즘 ( O(log N) ) 

• 자바에서는 [Arrays.binarySearch(배열, 찾는 값) return 위치] 함수가 존재한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] have = new int[N];
        for(int i = 0; i < N ; i++) {
            have[i] = Integer.parseInt(st.nextToken());
        }
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int[] haveYou = new int[M];
        
        for(int i = 0; i < M ; i++) {
            haveYou[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(have);
        
        for(int i = 0; i < M ; i++)
            binarySearch(haveYou[i], 0, have.length - 1 , 0, have);
        
        /*for(int i = 0; i < M; i ++) {
            int k = Arrays.binarySearch(have, haveYou[i]);
            if(k >= 0)
                System.out.print(1+" ");
            else
                System.out.print(0+" ");
        }*/
        
    }
    public static void binarySearch(int haveUone, int start, int end, int middle, int have[]) {
        //haveUone = 찾을거, start = 시작지점 , end = 끝지점 , m = 중간지점
        if(start > end) {
            System.out.print(0+" ");
            return;
        }// 없는 경우( + 1, - 1을 재귀로 반복해 주기 떄문에 start값이 end 값보다 커지는 경우가 존재한다 )
        
        middle = (start+end)/2;
        
        if(have[middle] == haveUone) {
            System.out.print(1+" ");
            return;
        }else if(haveUone > have[middle]) {
            binarySearch(haveUone, middle + 1, end, middle, have);
            // 찾는 값이 더 큰 경우, 오른쪽 탐색
        }else {
            binarySearch(haveUone, start, middle - 1, middle, have);
            // 찾는 값이 더 작은 경우, 왼쪽 탐색
        }
    }
    
}