Функция binarySearch

Функция binarySearch выполняет быстрый бинарный поиск элемента в отсортированной коллекции. Возвращает индекс найденного элемента или отрицательное число, если элемент не найден. Работает с массивами Array, списками List и отсортированными множествами Set.

Импорт

kotlinimport kotlin.collections.binarySearch

Синтаксис

kotlinfun <T : Comparable<T>> List<T?>.binarySearch(
  element: T?,
  fromIndex: Int = 0,
  toIndex: Int = size
): Int

kotlinfun <T> List<T>.binarySearch(
  element: T,
  comparator: Comparator<in T>,
  fromIndex: Int = 0,
  toIndex: Int = size
): Int

kotlinfun <T> Array<out T>.binarySearch(
  element: T,
  comparator: Comparator<in T>,
  fromIndex: Int = 0,
  toIndex: Int = size
): Int

Пример

Найдем элемент 3 в отсортированном списке:

kotlinval numbers = listOf(1, 2, 3, 4, 5)
val res = numbers.binarySearch(3)
println(res)

Результат выполнения кода:

kotlinInt 2

Пример

Поиск несуществующего элемента возвращает отрицательное число:

kotlinval numbers = listOf(1, 2, 3, 4, 5)
val res = numbers.binarySearch(6)
println(res)

Результат выполнения кода:

kotlinInt -6

Пример

Бинарный поиск в массиве с использованием компаратора:

kotlinval numbers = arrayOf(5, 4, 3, 2, 1)
val comparator = Comparator.reverseOrder<Int>()
val res = numbers.binarySearch(3, comparator)
println(res)

Результат выполнения кода:

kotlinInt 2

Пример

Поиск в части коллекции с указанием диапазона:

kotlinval numbers = listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
val res = numbers.binarySearch(3, 0, 5)
println(res)

Результат выполнения кода:

kotlinInt 2

Для каких коллекций работает

Функция binarySearch доступна для:

• Массивов Array
• Списков List
• Отсортированных множеств Set

Для словарей Map функция недоступна, так как они не являются упорядоченными коллекциями.

Смотрите также