binarySearch

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.

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.

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.

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 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.

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.

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.

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.

Exceptions

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

IllegalArgumentException - if fromIndex is greater than toIndex.

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.

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.

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.

Exceptions

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

IllegalArgumentException - if fromIndex is greater than toIndex.

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.