백준 1920 - 수 찾기

Java

1920 번 - 수 찾기

문제

접근 방법

이진 탐색 연습으로 해결하였다.
자바 라이브러리인 Array.binarySerach()를 사용하여도 되지만, 학습을 위해 직접 코딩하였다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, m, result;
	static int[] arr;
	static List<Integer> rs;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());

    	arr = new int[n];
    	stk = new StringTokenizer(br.readLine());
    	for(int i = 0; i < n; i++) {
    		arr[i] = stoi(stk.nextToken());
    	}

    	Arrays.sort(arr);
    	rs = new ArrayList<>();
    	m = stoi(br.readLine());
    	stk = new StringTokenizer(br.readLine());
    	for(int i = 0; i < m; i++) {
    		int curN = stoi(stk.nextToken());
    		if(binarySearch(curN, 0, arr.length - 1) != -1) {
    			System.out.println(1);
    		}
    		else
    			System.out.println(0);
    	}

    	br.close();
	}

	static int binarySearch(int target, int low, int high) {

		if(low <= high) {
			int mid = (low + high) / 2;

			if(target == arr[mid]) {
				return mid;
			}
			else if(arr[mid] < target) {	// 중간 값 보다, 주어진 값이 더 크면
				return binarySearch(target, mid + 1, high);
			}
			else {	// 중간 값 보다 주어진 값이 더 작으면
				return binarySearch(target, low, mid - 1);
			}
		}

		return -1;
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

그 외

한번 Arrays.binarySearch()를 뜯어 보았는데, 반복문으로 구현해 놓은 것을 보았다.

private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}