Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

21. 이분 탐색

이분 탐색 알고리즘을 배워 봅시다.

Java / Python

1. 수 찾기

1920번

배열을 정렬한 후 이분 탐색으로 값을 찾아 봅시다.

이번 문제는 N개의 정수가 주어져 있을 때, 이 안에 X라는 정수가 존재하는 지 알아내는 프로그램을 작성하는 문제입니다. N개의 정수(A[1]~A[N])가 주어지고, M개의 수를 입력 받아 이 M개의 수들이 A안에 존재하는 지 알아내는 것입니다.

• Java

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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] A = new int[N];
		for (int i = 0; i < N; i++) {
			A[i] = sc.nextInt();
		}
		Arrays.sort(A);
		int M = sc.nextInt();
		for (int i = 0; i < M; i++) {
			int num = sc.nextInt();
			int left = 0;
			int right = A.length - 1;
			boolean flag = false;
			while (left <= right) {
				int midIndex = (left + right) / 2;
				int midValue = A[midIndex];
				if (midValue > num) {
					right = midIndex - 1;
				} else if (midValue < num) {
					left = midIndex + 1;
				} else { // midValue = num
					flag = true;
					System.out.println(1);
					break;
				}
			}
			if (!flag) {
				System.out.println(0);
			}
		}
	}
}

• Python

import sys
N = int(sys.stdin.readline())
A = sorted(map(int,sys.stdin.readline().split()))
m = int(sys.stdin.readline())
nums = map(int, sys.stdin.readline().split())

def binary(k, A, start, end):
    if start > end:
        return 0
    m = (start + end)//2
    if k == A[m]:
        return 1
    elif k < A[m]:
        return binary(k, A, start, m-1)
    else:
        return binary(k, A, m+1, end)

for k in nums:
    start = 0
    end = len(A)-1
    print(binary(k,A,start,end))