binarySearch

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

Searches this list or its range for the provided element using the binary search algorithm. The list is expected to be sorted into ascending order according to the Comparable natural ordering of its elements, otherwise the result is undefined.

If the list contains multiple elements equal to the specified element, there is no guarantee which one will be found.

null value is considered to be less than any non-null value.

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
}

Return the index of the element, if it is contained in the list within the specified range; otherwise, the inverted insertion point (-insertion point - 1). The insertion point is defined as the index at which the element should be inserted, so that the list (or the specified subrange of list) still remains sorted.

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

Searches this list or its range for the provided element using the binary search algorithm. The list is expected to be sorted into ascending order according to the specified comparator, otherwise the result is undefined.

If the list contains multiple elements equal to the specified element, there is no guarantee which one will be found.

null value is considered to be less than any non-null value.

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
}

Return the index of the element, if it is contained in the list within the specified range; otherwise, the inverted insertion point (-insertion point - 1). The insertion point is defined as the index at which the element should be inserted, so that the list (or the specified subrange of list) still remains sorted according to the specified comparator.

Common
JVM
JS
Native
1.0
fun <T> List<T>.binarySearch(
    fromIndex: Int = 0,
    toIndex: Int = size,
    comparison: (T) -> Int
): Int

Searches this list or its range for an element for which comparison function returns zero using the binary search algorithm. The list is expected to be sorted into ascending order according to the provided comparison, otherwise the result is undefined.

If the list contains multiple elements for which comparison returns zero, there is no guarantee which one will be found.

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
}

Parameters

comparison - function that compares an element of the list with the element being searched.

Return the index of the found element, if it is contained in the list within the specified range; otherwise, the inverted insertion point (-insertion point - 1). The insertion point is defined as the index at which the element should be inserted, so that the list (or the specified subrange of list) still remains sorted.

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

Searches the array or the range of the array for the provided element using the binary search algorithm. The array is expected to be sorted according to the specified comparator, otherwise the result is undefined.

If the array contains multiple elements equal to the specified element, there is no guarantee which one will be found.

Return the index of the element, if it is contained in the array within the specified range; otherwise, the inverted insertion point (-insertion point - 1). The insertion point is defined as the index at which the element should be inserted, so that the array (or the specified subrange of array) still remains sorted according to the specified comparator.

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

Searches the array or the range of the array for the provided element using the binary search algorithm. The array is expected to be sorted, otherwise the result is undefined.

If the array contains multiple elements equal to the specified element, there is no guarantee which one will be found.

Return the index of the element, if it is contained in the array within the specified range; otherwise, the inverted insertion point (-insertion point - 1). The insertion point is defined as the index at which the element should be inserted, so that the array (or the specified subrange of array) still remains sorted.