Определение индекса заданного элемента в отсортированном массиве

Условие

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

Ответ

Для отсортированного по возрастанию массива используйте бинарный поиск: сравнивайте середину с целью и отбрасывайте половину диапазона. Время O(log n), дополнительная память O(1).

fun search(a: IntArray, target: Int): Int {
    var left = 0
    var right = a.lastIndex
    while (left <= right) {
        val mid = left + (right - left) / 2
        when {
            a[mid] < target -> left = mid + 1
            a[mid] > target -> right = mid - 1
            else -> return mid
        }
    }
    return -1
}

Пустой массив вернёт −1. При дублях возвращается одно из совпадений; для первого или последнего индексного вхождения нужны дополнительные правила сдвига границы.