백준 1920 수 찾기 | 자바 java | 이분 탐색 BinarySearch Scanner

 

이번 포스팅은 백준 1920번 수 찾기입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

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

1920번: 수 찾기

 

 

기본 알고리즘

• 자료 구조
• 정렬
• 이분 탐색

//오름차순으로 정렬된 배열에서 반복을 사용한 이분 탐색 코드

public static boolean binarySearch(int[] arr, int key){
        int low=0, high=arr.length-1;
        int mid=(low+high)/2;

        while(low<=high){
            mid=(low+high)/2;

            if(key==arr[mid]){
                return true;
            } else if(key<arr[mid]){
                high = mid-1;
            }
            else if(key>arr[mid]){
                low = mid+1;
            }
        }

        return false; 
    }

반응형

 

전체 코드

 

import java.util.Arrays;
import java.util.Scanner;
 
public class Main{
    public static boolean binarySearch(int[] arr, int key){
        int low=0, high=arr.length-1;
        int mid=(low+high)/2;
 
        while(low<=high){
            mid=(low+high)/2;
 
            if(key==arr[mid]){
                return true;
            } else if(key<arr[mid]){
                high = mid-1;
            }
            else if(key>arr[mid]){
                low = mid+1;
            }
        }
 
        return false; 
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=0, m=0;
        
        n=sc.nextInt();
        int nArr[] = new int[n];
        for(int i=0; i<n; i++){
            nArr[i]=sc.nextInt();
        }
 
        m=sc.nextInt();
        int mArr[] = new int[m];
        for(int i=0; i<m; i++){
            mArr[i]=sc.nextInt();
        }
 
        Arrays.sort(nArr);
 
        for(int i=0; i<m; i++){
            if(binarySearch(nArr, mArr[i])){
                System.out.println(1);
            } else {
                System.out.println(0);
            }
        }
 
        sc.close();
    }
}