binarySearch

kotlin-stdlib / kotlin.collections / binarySearch

Требования к платформе и версии: JVM (1.0), JS (1.0), Native (1.0)

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

Ищет в этом списке или его диапазоне указанный элемент с помощью алгоритма бинарного поиска. Ожидается, что список будет отсортирован в порядке возрастания в соответствии с естественным порядком элементов Comparable, в противном случае результат не определён.

Если список содержит несколько элементов, равных указанному элементу, нет гарантии, какой из них будет найден.

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). Точка вставки определяется как индекс, в который должен быть вставлен элемент, чтобы список (или указанный поддиапазон списка) оставался отсортированным.

Требования к платформе и версии: JVM (1.0), JS (1.0), Native (1.0)

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
}

Требования к платформе и версии: JVM (1.0), JS (1.0), Native (1.0)

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). Точка вставки определяется как индекс, в который должен быть вставлен элемент, чтобы список (или указанный поддиапазон списка) оставался отсортированным.

Требования к платформе и версии: JVM (1.0)

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). Точка вставки определяется как индекс, в который должен быть вставлен элемент, чтобы массив (или указанный поддиапазон массива) оставался отсортированным в соответствии с указанным компаратором.

END_OF_DOCUMENT_MARKER

Требования к платформе и версии: JVM (1.0)

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–2022 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