Kotlin 연습하기(6) - 선형/이진 검색

검색 알고리즘이란 무엇일까?

검색(Searching)은 배열이나 리스트 같은 데이터 집합에서 특정 값(또는 조건에 맞는 요소)을 찾아내는 과정이다.

예를 들어, 반에서 학생들 이름이 적힌 명단이 있을 때 "철수"라는 이름을 찾는 것과 비슷하다.

 

왜 검색이 필요할까?

• 데이터 찾기 : 많은 데이터 중에서 필요한 정보를 빠르게 찾기 위해 사용된다.
• 알고리즘 문제 : 코딩 테스트에서 특정 값을 찾는 문제가 출제된다.
• 효율성 : 올바른 검색 알고리즘을 사용하면 데이터의 양이 많더라도 빠른 시간 안에 원하는 값을 찾을 수 있다.

 

 

1. 선형 검색(Linear Search)

배열의 첫 번째 요소부터 순서대로 하나씩 검사하면서 찾고자 하는 값과 일치하는지 확인한다.

 

특징 

• 간단하고 구현하기 쉽다
• 데이터가 정렬되어 있지 않아도 사용할 수 있다.
• 최악의 경우 모든 요소를 확인해야 하므로, 시간 복잡도는 O(n)이다.

// 선형 검색 함수: 배열에서 target 값을 찾으면 해당 인덱스를 반환하고, 없으면 null 반환
fun linearSearch(arr: Array<Int>, target: Int): Int? {
    for (i in arr.indices) {
        if (arr[i] == target) {
            return i  // 찾은 경우 해당 인덱스 반환
        }
    }
    return null  // 값이 없으면 null 반환
}

fun main() {
    val numbers = arrayOf(5, 3, 8, 4, 2, 10)
    val target = 4
    val index = linearSearch(numbers, target)
    
    if (index != null) {
        println("선형 검색: $target 값은 인덱스 $index 에 있습니다.")
    } else {
        println("선형 검색: $target 값을 찾을 수 없습니다.")
    }
}

// arr.indices 는 배열의 인덱스 범위를 반환한다.
// 각 요소를 순차적으로 검사하여, target 값과 일치하면 해당 인덱스를 반환한다.

 

 

 

2. 이진 검색(Binary Search)

정렬된 배열을 반으로 나누어 원하는 값이 어느 쪽에 있는지 판단하여 검색 범위를 좁혀가는 방식이다.

 

특징

• 배열이 정렬되어 있어야 사용할 수 있다.
• 매 반복마다 검색 범위가 절반으로 줄어들기 때문에, 시간 복잡도는 O(log n)으로 매우 효율적이다.

// 이진 검색 함수: 정렬된 배열에서 target 값을 찾으면 해당 인덱스를 반환, 없으면 null 반환
fun binarySearch(arr: Array<Int>, target: Int): Int? {
    var low = 0
    var high = arr.size - 1

    while (low <= high) {
        val mid = (low + high) / 2  // 중간 인덱스 계산
        when {
            arr[mid] == target -> return mid  // 중간 값이 target이면 반환
            arr[mid] < target -> low = mid + 1  // target이 더 크면 오른쪽 범위로 좁힘
            else -> high = mid - 1              // target이 더 작으면 왼쪽 범위로 좁힘
        }
    }
    return null  // target 값을 찾지 못하면 null 반환
}

fun main() {
    val sortedNumbers = arrayOf(2, 3, 4, 5, 8, 10)  // 이진 검색을 위해 정렬된 배열 필요
    val target = 5
    val index = binarySearch(sortedNumbers, target)
    
    if (index != null) {
        println("이진 검색: $target 값은 인덱스 $index 에 있습니다.")
    } else {
        println("이진 검색: $target 값을 찾을 수 없습니다.")
    }
}


// 배열이 정렬되어 있다는 전제하에, low와 high 인덱스를 사용해 중간 mid을 계산한다.