176. 1920(수 찾기) - 자바

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

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		String[] tmp = br.readLine().split(" ");
		int[] A = new int[N];

		for (int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(tmp[i]);
		}

		Arrays.sort(A);

		int M = Integer.parseInt(br.readLine());
		tmp = br.readLine().split(" ");
		int[] B = new int[M];

		for (int i = 0; i < M; i++) {
			B[i] = Integer.parseInt(tmp[i]);
		}

		for (int val : B) {
			sb.append(binarySearch(A, val)).append("\n");
		}
		
		System.out.print(sb);
	}

	private static int binarySearch(int[] Array, int target) {
		int start = 0;
		int end = Array.length - 1;
		int mid = (start + end) / 2;

		while (end - start >= 0) {
			if (Array[mid] == target) return 1;
			else if (Array[mid] <= target) start = mid + 1;
			else end = mid - 1;
			
			mid = (start + end) / 2; 
		}
		return 0;
	}
}

문제요약

B의 숫자가 A안에 있는지 찾아보아라

설명

반복문을 사용해서 문제를 푼다면 시간초과가 발생할 수 있다.

때문에 이분탐색 기법을 사용해야 한다.

 

이분 탐색 기법은 간단히 말해 정렬된 배열에서 데이터를 찾으려는 시도할 때 탐색 범위를 절반씩 줄여가며 찾아가는 탐색 방법이다.

 

자세한 알고리즘 설명은 아래 링크에 설명되어 있다.

https://smhope.tistory.com/469?category=1056187 

[알고리즘 | 자료구조] 이분 탐색(Binary Search)