[백준] 이분 탐색 - 1920번 수 찾기 java 자바

문제

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

풀이

이분탐색 카테고리의 첫번재 문제이다. 원래 한 카테고리 끝나면 다음 카테고리를 진행하는 식으로 하려 했는데 여러 유형에 빨리 익숙해질 필요가 있는 거 같아 섞어서 풀고 있다.

이분탐색은 정렬된 배열을 왼쪽, 가운데, 오른쪽으로 나누어 가운데를 기준으로 값을 비교하며 탐색하는 알고리즘이다.

이 문제에선 배열의 길이가 N인 A 배열이 비교의 기준이 되기 때문에 이 배열이 정렬되어 있어야 한다.

나는 수업 때 배웠던 걸 더듬더듬 되짚어보면서 재귀를 사용하여 풀었는데 다른 분 블로그 보니까 그냥 반복문만 사용해서 푸는 거 같다...

 

코드

package 이분탐색;

import java.util.*;

public class No1920_수찾기 {

	static int[] A;
	static int[] B;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		A = new int[N];
		for (int i = 0; i < N; i++) {
			A[i] = sc.nextInt();
		}

		Arrays.sort(A);

		int M = sc.nextInt();
		B = new int[M];
		for (int i = 0; i < M; i++) {
			B[i] = sc.nextInt();
		}
		
		for(int compare:B) {
			System.out.println(solution(0, (N-1)/2, N-1, compare));
		}
	}

	static int solution(int left, int mid, int right, int compare) {
		while (left<=right) {
			if (compare == A[mid]) {
				return 1;
			} else if (compare < A[mid]) {
				return solution(left, (left + mid-1) / 2, mid - 1, compare);
			} else {
				return solution(mid+1, (mid+1+right)/2, right, compare);
			}
		}
		
		return 0;
	}

}