[kotlin] 코틀린으로 이진 탐색 알고리즘 작성하기
이진 탐색(Binary Search) 알고리즘은 주어진 배열 내에서 특정 값의 위치를 찾거나 삽입할 위치를 찾는 데 사용됩니다. 이 알고리즘은 배열이 정렬되어 있다는 가정 하에 동작하며, 매 단계마다 배열의 중간 값과 대상 값을 비교해 대상 값이 중간 값의 왼쪽 또는 오른쪽에 위치하는지를 확인합니다.
이진 탐색 알고리즘의 구현
다음은 코틀린으로 이진 탐색 알고리즘을 구현한 예제 코드입니다.
fun binarySearch(arr: IntArray, target: Int): Int {
var left = 0
var right = arr.size - 1
while (left <= right) {
val mid = left + (right - left) / 2
when {
arr[mid] == target -> return mid
arr[mid] < target -> left = mid + 1
else -> right = mid - 1
}
}
return -1
}
위의 코드는 정렬된 정수 배열과 찾고자 하는 값이 주어졌을 때, 해당 값의 인덱스를 반환하는 binarySearch
함수를 구현한 것입니다.
동작 확인
fun main() {
val arr = intArrayOf(2, 4, 6, 8, 10, 12, 14, 16, 18, 20)
val target = 14
val index = binarySearch(arr, target)
if (index != -1) {
println("값 $target 는 배열의 $index 번째에 위치합니다.")
} else {
println("값 $target 가 배열에 존재하지 않습니다.")
}
}
위의 main
함수에서는 binarySearch
함수를 사용하여 14라는 값을 배열에서 찾고, 결과를 출력합니다.
이렇게 코틀린으로 이진 탐색 알고리즘을 구현하고 활용할 수 있습니다.