[BOJ 실버4 JAVA] 1920 수 찾기 - 이진 탐색

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

1920번: 수 찾기

BOJ 1920

- 처음에는 N개의 숫자가 주어지고, 그 후 M개의 숫자가 주어지는데, 후에 주어진 M개의 숫자가 N에 존재하면 1, 존재하지 않으면 0을 출력하는 문제이다.

- 다양한 탐색 알고리즘이 존재하지만, 이분 탐색 알고리즘을 연습할 겸 문제를 시도했다.

 

 

package p220214;

import java.util.Arrays;
import java.util.Scanner;

public class BOJ1920_이진탐색연습 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();                       ---- 1. 정수 N 입력
		int[] NList = new int[N];                   ---- 2. N의 크기를 갖는 NList 선언
		for(int i=0; i<N; i++) {
			NList[i] = sc.nextInt();                ---- 3. NList에 입력
		}
		int M = sc.nextInt();                       ---- 4. 정수 M 입력
		int[] MList = new int[M];                   ---- 5. M의 크기를 갖는 MList 선언
		for(int i=0; i<M; i++) {
			MList[i] = sc.nextInt();                ---- 6. MList에 입력
		}
		Arrays.sort(NList);                         ---- 7. 이진탐색은 시간복잡도가 짧지만,
                                                    ----    탐색 전에 정렬이 되어있어야 한다는 조건이 있다.
		
		for(int i=0; i<M; i++) {
			System.out.println(BS(NList, MList[i]));
		}
	}
	
	public static int BS(int[] arr, int key) {       ---- 이진 탐색 함수 ----
		int st = 0;                                  ---- 1. 시작 index = 0
		int ed = arr.length-1;                       ---- 2. 끝 index = arr배열의 길이 -1  
		while(st <= ed) {                            ---- 3. 끝 index가 시작 idex보다 크거나 같아질 때까지 반복
			int mid = (st+ed)/2;					 ---- 4. 중간 index : 매번 바뀌어야하므로 while문 안에 선언
			if(arr[mid]==key) {						 ---- 5. 중간 값이 찾으려고자 하는 값(key)와 같다면 1반환
				return 1;
			} else if(arr[mid] > key) {				 ---- 6. 중간 값이 key보다 작다면 끝 index를 mid로 설정
				ed = mid - 1; 						 
			} else {								 ---- 7. 중간 값이 key보다 크면 시작 index를 mid로
				st = mid + 1;
			}
		}
		return 0;									 ---- 8. while문이 끝나도 못 찾으면 0반환
	}
}