https://www.acmicpc.net/problem/1920
1920번: 수 찾기
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들
www.acmicpc.net
가장 기본적인 이분탐색 알고리즘으로 해결 가능한 문제입니다.
주의할 점은 처음에 주어지는 배열의 크기인 N과
수가 배열안에 존재하는지 확인하는 배열의 크기인 M
둘의 크기가 다르다는 것입니다..
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int list[]; static int ques[]; static int N, M; static int binarysearch(int l, int r, int x) { if (l > r) return 0; int m = (l + r) / 2; if (list[m] == x) return 1; else { if (list[m] > x) return binarysearch(l, m - 1, x); else return binarysearch(m + 1, r, x); } } static void func() { for (int i = 1; i <= M; i++) { System.out.println(binarysearch(1, N, ques[i])); } } static void input() throws Exception { st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); list = new int[N + 1]; st = new StringTokenizer(br.readLine()); for (int i = 1; i <= N; i++) { list[i] = Integer.parseInt(st.nextToken()); } Arrays.sort(list); st = new StringTokenizer(br.readLine()); M = Integer.parseInt(st.nextToken()); ques = new int[M + 1]; st = new StringTokenizer(br.readLine()); for (int i = 1; i <= M; i++) { ques[i] = Integer.parseInt(st.nextToken()); } } public static void main(String[] args) throws Exception { input(); func(); } } | cs |
'algorithm > binarysearch' 카테고리의 다른 글
| boj 2110 공유기 설치 (0) | 2021.04.13 |
|---|---|
| boj 7453 합이 0인 네 정수 (0) | 2021.01.22 |
| boj 2143 두 배열의 합 (0) | 2021.01.22 |
| boj 2805 나무 자르기 (0) | 2021.01.22 |
| boj 17124 두 개의 배열 (0) | 2021.01.22 |