백준 1920번: 수 찾기 [이분탐색] - Java

www.acmicpc.net/problem/1920

1920번: 수 찾기

이분탐색이 아닌 Java의 Arrays 클래스에 있는 binarySearch() 메소드 활용

binarySearch함수는 1번째 매개변수로 배열을 넣고 2번째 매개변수에 찾으려는 값을 넣으면

그 값이 배열에 있다면 해당 인덱스를 리턴해주고 없다면 있는 수들 사이에서 비어있는 값의 음수로 반환해준다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static int N, M;
	public static int[] arr;
	// public static int[] mArr;

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		arr = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		// 이분탐색을 위한 오름차순 정렬
		Arrays.sort(arr);

		M = Integer.parseInt(br.readLine());
		// nArr = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			int num = Integer.parseInt(st.nextToken());
			
			int val = Arrays.binarySearch(arr, num);
//			System.out.println(val);
			if (val < 0) {
				System.out.println(0);
			} else {
				System.out.println(1);
			}

		}

	}

}

 

 

직접 구현한 이분탐색으로 푼 코드

 

cjh5414.github.io/binary-search/블로그가 설명이 잘되어있다.

 

배열을 정렬해놓고 반을 나눠 가장 중간값과 비교해서 작다면 왼쪽부분을 다시 비교하고 크다면 오른쪽부분을 다시 비교하는 것이다.

종료조건은..

1. 일치하는 값이 나오면 종료

2. 배열자체에 일치하는 값이 없을경우에는 배열의 범위를 벗어나면 종료

이 경우에는 배열을 반으로 나누면서 비교를하며 계속 start와 end를 수정하다가보면

어느순간 start범위가 end보다 커지게된다. 이때 배열의 범위를 벗어났기 때문에 일치하는 값이 없다는 것으로 간주하고 종료를 한다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static int N, M;
	public static int[] arr;

	public static void main(String[] args) throws NumberFormatException, IOException {


		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		arr = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		// 이분탐색을 위한 오름차순 정렬
		Arrays.sort(arr);

		M = Integer.parseInt(br.readLine());
		// nArr = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			int num = Integer.parseInt(st.nextToken());
			int start = 0;
			int end = N-1;
			
			//종료조건 - start의 크기가 end보다 더 큰가?
			while(start <= end) {
				int mid = (start+end) /2;
				if(arr[mid] < num ) {
					start = mid+1;
				} else if(arr[mid] > num) {
					end = mid-1;
				}else {
					System.out.println(1);
					break;
				}
				
			}
			if(start>end)
				System.out.println(0);

		}

	}

}