Binary Search(이진/이분 탐색)

Q. 이진 탐색(또는 이분 탐색)은 무엇인가?

A. 정렬된 배열에서 원하는 값을 빠르게 찾아내기 위한 검색 알고리즘 중 하나입니다. 이 알고리즘은 배열 내의 값을 반복해서 절반씩 나누어 찾아가는 방법을 사용합니다. 주로 큰 데이터 집합에서 빠른 검색이 필요한 경우에 사용됩니다.

Q. 이진 탐색의 기본 작동 원리는?

A.
기본 조건 : 주어진 배열은 정렬되어 있어야 합니다. (오름차순 또는 내림차순)

1. 탐색하려는 값(검색 대상)과 배열의 중간 요소를 비교합니다.

2. 중간 요소와 검색 대상이 같다면 원하는 값을 찾은 것이므로 중간 요소의 인덱스를 반환합니다.

3. 중간 요소가 검색 대상보다 크다면, 검색 범위를 배열의 왼쪽 절반으로 좁힙니다. 중간 요소의 왼쪽 하위 배열에 대해 재귀적으로 이진 탐색을 수행합니다.

4. 중간 요소가 검색 대상보다 작다면, 검색 범위를 배열의 오른쪽 절반으로 좁힙니다. 중간 요소의 오른쪽 하위 배열에 대해 재귀적으로 이진 탐색을 수행합니다.

5. 검색 범위가 더 이상 좁혀지지 않을 때까지 위 과정을 반복합니다.

6. 검색 대상을 찾지 못한 경우, 검색 범위가 더 이상 없어지고 탐색이 종료됩니다. 이 경우 -1이나 다른 특별한 값을 반환하여 검색 실패를 나타냅니다.

 이진 탐색은 검색 범위를 반으로 나누기 때문에 검색 속도가 매우 빠르며, 시간 복잡도는 O(log n)입니다. 이 알고리즘은 배열이나 리스트와 같은 정렬된 데이터 구조에서 효과적으로 사용할 수 있습니다.

 

fun BinarySearch(Arr: List<Int>, SearchNum: Int, Start: Int, End: Int): Int {
    if (Start > End) {
        return -1
    }

    val mid = (Start + End) / 2

    return if (Arr[mid] == SearchNum) {
        mid
    } else if (Arr[mid] > SearchNum) {
        BinarySearch(Arr, SearchNum, Start, mid - 1)
    } else {
        BinarySearch(Arr, SearchNum, mid + 1, End)
    }
}