Бинарный поиск

Описание: Эффективный алгоритм для поиска в отсортированном массиве, который последовательно делит массив пополам.
Когда использовать: Полезен для больших массивов, если они отсортированы.

fun binarySearch(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1

    while (left <= right) {
        val mid = left + (right - left) / 2
        when {
            nums[mid] == target -> return mid
            nums[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }

    return -1
}

// Пример использования:
val sortedNums = intArrayOf(1, 2, 4, 7, 9)
val target = 7
println(binarySearch(sortedNums, target)) // Вывод: 3

Дан отсортированный массив целых чисел и целевое значение. Напишите функцию, которая использует бинарный поиск для нахождения индекса целевого значения в массиве. Если целевое значение не найдено, верните -1.

fun search(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1

    while (left <= right) {
        val mid = left + (right - left) / 2

        when {
            nums[mid] == target -> return mid
            nums[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }

    return -1
}