[BOJ] 수 찾기

난이도 : Sliver 4

문제링크

• N개의 정수가 주어질 때, 이 안에 X라는 정수가 존재하는 지 여부를 리턴하라

 

해설

전체코드 보기

 

1. A배열 정렬하기

    static int N, M;
    static int[] A, B;
    public static void main(String[] args) throws IOException {
        init();
        Arrays.sort(A);
        for (int i = 0; i < M; i++) {
            binarySearch(i);
        }
    }

• 이분탐색을 활용하기 위해 A배열을 정렬합니다.

 

2. 이분탐색을 통해 검색하기

private static void binarySearch(int idx) {
    int left = 0, right = A.length-1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (A[mid] == B[idx]) {
            System.out.println(1);
            return;
        } else if (A[mid] > B[idx]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    System.out.println(0);
}

• 정렬된 배열일 경우, 범위를 좁혀가며 원하는 숫자를 찾는 이분탐색을 활용할 수 있습니다.
• 투포인터를 사용하여 두 포인터의 중간에 위치한 값이 원하는 값인지 확인합니다.
  • 중간값이 찾고자 하는 값보다 크다면 범위를 중간 ~ 끝으로 옮겨 탐색합니다.
  • 중간값이 찾고자 하는 값보다 작다면 범위를 처음 ~ 중간으로 옮겨 탐색합니다.
  • 왼쪽 포인터가 오른쪽 포인터보다 작을때까지 반복합니다.