Функция binarySearch
Функция binarySearch выполняет быстрый бинарный поиск
элемента в отсортированной коллекции. Возвращает индекс
найденного элемента или отрицательное число, если элемент
не найден. Работает с массивами Array, списками
List и отсортированными множествами Set.
Импорт
import kotlin.collections.binarySearch
Синтаксис
fun <T : Comparable<T>> List<T?>.binarySearch(
element: T?,
fromIndex: Int = 0,
toIndex: Int = size
): Int
fun <T> List<T>.binarySearch(
element: T,
comparator: Comparator<in T>,
fromIndex: Int = 0,
toIndex: Int = size
): Int
fun <T> Array<out T>.binarySearch(
element: T,
comparator: Comparator<in T>,
fromIndex: Int = 0,
toIndex: Int = size
): Int
Пример
Найдем элемент 3 в отсортированном списке:
val numbers = listOf(1, 2, 3, 4, 5)
val res = numbers.binarySearch(3)
println(res)
Результат выполнения кода:
Int 2
Пример
Поиск несуществующего элемента возвращает отрицательное число:
val numbers = listOf(1, 2, 3, 4, 5)
val res = numbers.binarySearch(6)
println(res)
Результат выполнения кода:
Int -6
Пример
Бинарный поиск в массиве с использованием компаратора:
val numbers = arrayOf(5, 4, 3, 2, 1)
val comparator = Comparator.reverseOrder<Int>()
val res = numbers.binarySearch(3, comparator)
println(res)
Результат выполнения кода:
Int 2
Пример
Поиск в части коллекции с указанием диапазона:
val numbers = listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
val res = numbers.binarySearch(3, 0, 5)
println(res)
Результат выполнения кода:
Int 2
Для каких коллекций работает
Функция binarySearch доступна для:
- Массивов
Array - Списков
List - Отсортированных множеств
Set
Для словарей Map функция недоступна,
так как они не являются упорядоченными коллекциями.
