[Kotlin] 이진 탐색 알고리즘

이진 탐색이란?

• 정렬된 리스트의 중간 값을 이용해 검색 값을 줄여 가면서 원하는 값을 찾는 알고리즘

 

탐색 과정

출처: 나무위키

1. 정렬된 리스트의 중간값을 찾는다.
2. 찾는 수가 중간값보다 크면 오른쪽으로, 작으면 왼쪽으로 검색 범위를 좁힌다.
3. 1, 2번을 반복한다.

이 과정을 반복하면 그냥 반복문을 이용해 찾는 것보다 더 빠르게 원하는 숫자를 찾을 수 있다.

 

예제 코드

숫자의 범위와 원하는 숫자를 입력하고 이진 탐색으로 그 숫자를 찾는 알고리즘

package algorithm

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val bf = BufferedReader(InputStreamReader(System.`in`))
    val arrayIndex = bf.readLine().toInt()

    val array = IntArray(arrayIndex)
    repeat(arrayIndex) {
        array[it] = it+1
    }

    val searchData = bf.readLine().toInt()

    println(binarySearch(array, searchData, 0, array.lastIndex))
}

fun binarySearch(array: IntArray, searchData: Int, low: Int, high: Int): Int {
    // 값을 찾을 수 없는 경우
    if (low > high) return -1

    // 중앙 값 결정하기
//    val mid = low + (high - low)/2    범위를 넘어서는 경우 구현
    val mid = (high+low)/2

    return if (array[mid] == searchData) {
        array[mid]
    } else if (array[mid] > searchData) {   // 찾는 값이 데이터보다 큼
        binarySearch(array, searchData, low, mid-1)
    } else {    // 찾는 값이 데이터보다 작음
        binarySearch(array, searchData, mid+1, high)
    }
}

 

---

과정

1. 숫자를 입력받아 배열의 범위를 정한다.
2. repeat 문을 이용해 배열에 값을 넣는다.
3. 탐색할 숫자를 입력한다.
4. 이진 탐색으로 결과를 도출한다.
5. 찾는 값이 크면 last index를 mid-1 로 적용해 탐색 범위를 왼쪽으로 제한하고, 작은 경우 first index를 min+1로 적용해 탐색 범위를 오른쪽으로 제한한다.
6. 5번 과정을 반복해 원하는 값을 출력한다.

결과

 

 

연습 문제

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

10815번: 숫자 카드

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

1920번: 수 찾기