binarySearch
fun <T : Comparable<T>> List<T?>.binarySearch( element: T?, fromIndex: Int = 0, toIndex: Int = size ): Int
Ищет в этом списке или его диапазоне заданный элемент с помощью алгоритма бинарного поиска. Ожидается, что список отсортирован в порядке возрастания по естественному порядку сравнения элементов, в противном случае результат не определен.
Если список содержит несколько элементов, равных указанному элементу, нет гарантии, какой из них будет найден.
null значение считается меньше любого ненулевого значения.
import kotlin.test.*
fun main(args: Array<String>) {
//sampleStart
val list = mutableListOf('a', 'b', 'c', 'd', 'e')
println(list.binarySearch('d')) // 3
list.remove('d')
val invertedInsertionPoint = list.binarySearch('d')
val actualInsertionPoint = -(invertedInsertionPoint + 1)
println(actualInsertionPoint) // 3
list.add(actualInsertionPoint, 'd')
println(list) // [a, b, c, d, e]
//sampleEnd
}import kotlin.test.*
fun main(args: Array<String>) {
//sampleStart
val list = listOf('a', 'b', 'c', 'd', 'e')
println(list.binarySearch('d')) // 3
// element is out of range from the left
println("list.binarySearch('b', fromIndex = 2) < 0 is ${list.binarySearch('b', fromIndex = 2) < 0}") // true
// element is out of range from the right
println("list.binarySearch('d', toIndex = 2) < 0 is ${list.binarySearch('d', toIndex = 2) < 0}") // true
//sampleEnd
}Возвращает индекс элемента, если он содержится в списке в указанном диапазоне; в противном случае инвертированную точку вставки (-insertion point - 1). Точка вставки определяется как индекс, в который следует вставить элемент, чтобы список (или указанный поддиапазон списка) оставался отсортированным.
fun <T> List<T>.binarySearch( element: T, comparator: Comparator<in T>, fromIndex: Int = 0, toIndex: Int = size ): Int
Ищет в этом списке или его диапазоне заданный элемент с помощью алгоритма бинарного поиска. Ожидается, что список отсортирован в порядке возрастания согласно указанному компаратору, в противном случае результат не определен.
Если список содержит несколько элементов, равных указанному элементу, нет гарантии, какой из них будет найден.
null значение считается меньше любого ненулевого значения.
import kotlin.test.*
fun main(args: Array<String>) {
//sampleStart
val colors = listOf("Blue", "green", "ORANGE", "Red", "yellow")
println(colors.binarySearch("RED", String.CASE_INSENSITIVE_ORDER)) // 3
//sampleEnd
}Возвращает индекс элемента, если он содержится в списке в указанном диапазоне; в противном случае инвертированную точку вставки (-insertion point - 1). Точка вставки определяется как индекс, в который следует вставить элемент, чтобы список (или указанный поддиапазон списка) оставался отсортированным по указанному компаратору.
fun <T> List<T>.binarySearch( fromIndex: Int = 0, toIndex: Int = size, comparison: (T) -> Int ): Int
Ищет в этом списке или его диапазоне элемент, для которого заданная функция сравнения возвращает ноль с помощью алгоритма бинарного поиска.
Ожидается, что список отсортирован таким образом, чтобы знаки возвращаемых значений функции сравнения возрастали по элементам списка, т.е. отрицательные значения идут перед нулем, а нули — перед положительными. В противном случае результат не определен.
Если список содержит несколько элементов, для которых сравнение возвращает ноль, нет гарантии, какой из них будет найден.
import kotlin.test.*
fun main(args: Array<String>) {
//sampleStart
data class Box(val value: String)
val values = listOf("A", "ant", "binding", "Box", "cell")
val boxes = values.map { Box(it) }
val valueToFind = "box"
// `boxes` list is sorted according to the following comparison function
val index = boxes.binarySearch { String.CASE_INSENSITIVE_ORDER.compare(it.value, valueToFind) }
if (index >= 0) {
println("Value at $index is ${boxes[index]}") // Value at 3 is Box(value=Box)
} else {
println("Box with value=$valueToFind was not found")
}
//sampleEnd
}Параметры
comparison - функция, которая возвращает ноль при вызове на элементе списка, который ищется. Для элементов, предшествующих целевому элементу, функция должна возвращать отрицательные значения; для элементов, следующих за целевым элементом, — положительные.
Возвращает индекс найденного элемента, если он содержится в списке в указанном диапазоне; в противном случае инвертированную точку вставки (-insertion point - 1). Точка вставки определяется как индекс, в который следует вставить элемент, чтобы список (или указанный поддиапазон списка) оставался отсортированным.
fun <T> Array<out T>.binarySearch( element: T, comparator: Comparator<in T>, fromIndex: Int = 0, toIndex: Int = size ): Int
Ищет в массиве или в заданном диапазоне массива заданный элемент с помощью алгоритма бинарного поиска. Ожидается, что массив отсортирован по указанному компаратору, в противном случае результат не определен.
Если массив содержит несколько элементов, равных заданному элементу, нет гарантии, какой из них будет найден.
Параметры
element - искомый элемент.
comparator - компаратор, по которому отсортирован массив.
fromIndex - начало диапазона (включительно), по умолчанию 0.
toIndex - конец диапазона (исключительно), по умолчанию размер массива.
Исключения
IndexOutOfBoundsException - если fromIndex меньше нуля или toIndex больше размера массива.
IllegalArgumentException - если fromIndex больше toIndex.
Возвращает индекс элемента, если он содержится в массиве в указанном диапазоне; в противном случае инвертированную точку вставки (-insertion point - 1). Точка вставки определяется как индекс, в который следует вставить элемент, чтобы массив (или указанный поддиапазон массива) оставался отсортированным по указанному компаратору.
fun <T> Array<out T>.binarySearch( element: T, fromIndex: Int = 0, toIndex: Int = size ): Int
fun ByteArray.binarySearch( element: Byte, fromIndex: Int = 0, toIndex: Int = size ): Int
fun ShortArray.binarySearch( element: Short, fromIndex: Int = 0, toIndex: Int = size ): Int
fun IntArray.binarySearch( element: Int, fromIndex: Int = 0, toIndex: Int = size ): Int
fun LongArray.binarySearch( element: Long, fromIndex: Int = 0, toIndex: Int = size ): Int
fun FloatArray.binarySearch( element: Float, fromIndex: Int = 0, toIndex: Int = size ): Int
fun DoubleArray.binarySearch( element: Double, fromIndex: Int = 0, toIndex: Int = size ): Int
fun CharArray.binarySearch( element: Char, fromIndex: Int = 0, toIndex: Int = size ): Int
@ExperimentalUnsignedTypes fun UIntArray.binarySearch( element: UInt, fromIndex: Int = 0, toIndex: Int = size ): Int
@ExperimentalUnsignedTypes fun ULongArray.binarySearch( element: ULong, fromIndex: Int = 0, toIndex: Int = size ): Int
@ExperimentalUnsignedTypes fun UByteArray.binarySearch( element: UByte, fromIndex: Int = 0, toIndex: Int = size ): Int
@ExperimentalUnsignedTypes fun UShortArray.binarySearch( element: UShort, fromIndex: Int = 0, toIndex: Int = size ): Int
Ищет в массиве или диапазоне массива указанный элемент с помощью алгоритма бинарного поиска. Массив предполагается отсортированным; в противном случае результат не определён.
Если массив содержит несколько элементов, равных заданному элементу, нет гарантии, какой из них будет найден.
Параметры
element - элемент для поиска.
fromIndex - начало диапазона (включительно) для поиска, по умолчанию 0.
toIndex - конец диапазона (исключительно) для поиска, по умолчанию размер массива.
Исключения
IndexOutOfBoundsException - если fromIndex меньше нуля или toIndex больше размера массива.
IllegalArgumentException - если fromIndex больше, чем toIndex.
Возвращает индекс элемента, если он содержится в массиве в указанном диапазоне; в противном случае, инвертированную точку вставки (-insertion point - 1). Точка вставки определяется как индекс, в который элемент должен быть вставлен, чтобы массив (или указанный поддиапазон массива) оставался отсортированным.
© 2010–2020 JetBrains s.r.o. and Kotlin Programming Language contributors
Licensed under the Apache License, Version 2.0.
https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/binary-search.html
