package baekjoon;
import java.util.Arrays;
import java.util.Scanner;
public class b1920 {
public static int search(int[] arr, int keyValue) {
int low = 0;
int high = arr.length-1;
int mid = 0;
while(low <= high) {
mid = (low+high) / 2;
if(arr[mid] == keyValue) return 1;
else if(arr[mid] > keyValue) high = mid-1;
else if(arr[mid] < keyValue) low = mid+1;
}
return 0;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int arr[] = new int[N];
for(int i = 0; i < N; i++) arr[i] = sc.nextInt();
Arrays.sort(arr);
int M = sc.nextInt();
int[] arr2 = new int[M];
for(int i = 0; i < M; i++) arr2[i] = sc.nextInt();
for(int i = 0; i < M; i++) System.out.println(search(arr, arr2[i]));
}
}
이분 탐색 문제!
https://st-lab.tistory.com/261
[백준] 1920번 : 수 찾기 - JAVA [자바]
https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어..
st-lab.tistory.com
이 분 글을 보면 정말 쏙쏙 이해가 잘 된다.
for문 돌려서 노가다하면 시간초과 뜸. 이분탐색 활용 잘 하자.
'Problems & Solutions' 카테고리의 다른 글
2559 수열 (0) | 2022.08.08 |
---|---|
10816 숫자 카드2 (0) | 2022.08.05 |
19941 햄버거 분배 (0) | 2022.08.05 |
7795 먹을 것인가 먹힐 것인가 (0) | 2022.07.30 |
9095 1, 2, 3 더하기 (0) | 2022.07.30 |