[백준 N1920] 이진탐색.수찾기

문제

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

입력

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력 

5

4 1 5 2 3

5

1 3 7 9 5

예제 출력 

1

1

0

0

1

import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    sc.nextLine()
    val A = sc.nextLine().split(" ").filter { it != " " }.map { it.toInt() }.sorted()
    val m = sc.nextInt()
    sc.nextLine()
    val B = sc.nextLine().split(" ").filter { it != " " }.map { it.toInt() }

    for (i in 0 until m)
        (println(BinarySearch(A, B[i])))


}

fun BinarySearch(A: List<Int>, target: Int): Int {
    var low = 0
    var high = A.size - 1
    var mid: Int

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

        if (A[mid] == target)
            return 1
        else if (A[mid] > target)
            high = mid - 1
        else
            low = mid + 1
    }
    return 0


}

A와 B 값 들을 String 값으로 받아와 공백단위로 잘라서 Int로 값들을 변환해 한번에 값을 받아왔습니다.

 

이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘입니다.

배열의 중간에 있는 임의의 값 mid 를 선택하여 target 과 비교해서 찾아냅니다.

target이  mid 보다 작으면 mid를 기준으로 좌측의 데이터들을 대상으로, target이 mid 보다 크면 배열의 우측을 대상으로 다시 탐색합니다.

동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교합니다. 해당 값을 찾을 때까지 이 과정을 반복합니다.

 

문제 출처 :https://www.acmicpc.net/problem/1920

이진 탐색 개념: https://cjh5414.github.io/binary-search/