kotlin-stdlib/kotlin.collections/binarySearch

binarySearch

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

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.

Since Kotlin

1.0

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.

Parameters

element

the element to search for.

comparator

the comparator according to which this array is sorted.

fromIndex

the start of the range (inclusive) to search in, 0 by default.

toIndex

the end of the range (exclusive) to search in, size of this array by default.

Throws

if fromIndex is less than zero or toIndex is greater than the size of this array.

if fromIndex is greater than toIndex.

fun <T> Array<out T>.binarySearch(element: T, fromIndex: Int = 0, toIndex: Int = size): Int(source)
fun ByteArray.binarySearch(element: Byte, fromIndex: Int = 0, toIndex: Int = size): Int(source)
fun ShortArray.binarySearch(element: Short, fromIndex: Int = 0, toIndex: Int = size): Int(source)
fun IntArray.binarySearch(element: Int, fromIndex: Int = 0, toIndex: Int = size): Int(source)
fun LongArray.binarySearch(element: Long, fromIndex: Int = 0, toIndex: Int = size): Int(source)
fun FloatArray.binarySearch(element: Float, fromIndex: Int = 0, toIndex: Int = size): Int(source)
fun DoubleArray.binarySearch(element: Double, fromIndex: Int = 0, toIndex: Int = size): Int(source)
fun CharArray.binarySearch(element: Char, fromIndex: Int = 0, toIndex: Int = size): Int(source)

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.

Since Kotlin

1.0

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.

Parameters

element

the to search for.

fromIndex

the start of the range (inclusive) to search in, 0 by default.

toIndex

the end of the range (exclusive) to search in, size of this array by default.

Throws

if fromIndex is less than zero or toIndex is greater than the size of this array.

if fromIndex is greater than toIndex.

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

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.

Since Kotlin

1.0

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.

Samples

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.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(source)

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.

Since Kotlin

1.0

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.

Samples

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(source)

Searches this list or its range for an element for which the given comparison function returns zero using the binary search algorithm.

The list is expected to be sorted so that the signs of the comparison function's return values ascend on the list elements, i.e. negative values come before zero and zeroes come before positive values. 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.

Since Kotlin

1.0

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.

Parameters

comparison

function that returns zero when called on the list element being searched. On the elements coming before the target element, the function must return negative values; on the elements coming after the target element, the function must return positive values.

Samples

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
}