binarySearch

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

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

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

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

null значение считается меньшим любого ненулевого значения.

Примеры

import kotlin.math.*
import kotlin.test.*

fun main() { 
   //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.math.*
import kotlin.test.*

fun main() { 
   //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
}

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

Выполняет поиск указанного элемента в этом списке или его диапазоне с помощью алгоритма бинарного поиска. Предполагается, что список отсортирован по возрастанию в соответствии с указанным компаратором; в противном случае результат не определён.

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

null значение считается меньшим любого ненулевого значения.

Примеры

import kotlin.math.*
import kotlin.test.*

fun main() { 
   //sampleStart 
   val colors = listOf("Blue", "green", "ORANGE", "Red", "yellow")
println(colors.binarySearch("RED", String.CASE_INSENSITIVE_ORDER)) // 3 
   //sampleEnd
}

fun <T> List<T>.binarySearch(fromIndex: Int = 0, toIndex: Int = size, comparison: (T) -> Int): Int

Выполняет поиск элемента в этом списке или его диапазоне с помощью алгоритма бинарного поиска. Для найденного элемента заданная функция сравнения должна возвращать ноль.

Предполагается, что список отсортирован так, что знаки значений, возвращаемых функцией сравнения, возрастают при переходе по элементам списка: отрицательные значения идут перед нулём, а нули — перед положительными значениями. В противном случае результат не определён.

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

Параметры

Примеры

import kotlin.math.*
import kotlin.test.*

fun main() { 
   //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
}

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

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

Выполняет поиск указанного элемента в массиве или его диапазоне с помощью алгоритма бинарного поиска. Предполагается, что массив отсортирован в соответствии с указанным компаратором; в противном случае результат не определён.

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

Параметры

Исключения

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

Выполняет поиск указанного элемента в массиве или его диапазоне с помощью алгоритма бинарного поиска. Предполагается, что массив отсортирован; в противном случае результат не определён.

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

Параметры

Исключения