Hi, I was interested in suggesting a new standard ...

# stdlib

[Trevor Hackman]

Hi, I was interested in suggesting a new standard library function in kotlin.collections and in writing it myself and making a pull request to contribute,

Is this something that would be of interest? I found myself wanting this function but it not existing in the standard library, it would be binarySearchIndexed

With a signature of perhaps

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

Thread in Slack Conversation

[Derek Peirce]

What would be the advantage here of using an index to represent the compare-to element instead of the element itself with a traditional Comparator?

[Trevor Hackman]

It's not instead of it's in addition to. Same pattern as forEachIndexed.

[Derek Peirce]

But what's your use case?

[gildor]

Looks very specific for stdlib IMO

[Trevor Hackman]

Avoiding the need to write a boilerplate binary search function for example when wanting to find the median of two sorted lists in log time.

[Derek Peirce]

That sounds like a relatively obscure use-case, I agree with Andrey. Perhaps the stdlib would best include a very general binary search method that, via inline methods, could be repurposed for any data structure.

[Trevor Hackman]

I can't figure out, how would you get indexes for a binary search via inline methods on the general binarySearch? And keep time complexity log(n)

[Derek Peirce]

Something like this, based on code from here:

inline fun binarySearch(min: Int = 0, max: Int, comparison: (Int) -> Int) : Int {
    var low = min
    var high = max
    var mid: Int
    while(low <= high) {
        mid = low + ((high - low) / 2)
        val result = comparison(mid)
        when {
            result > 0   -> low = mid + 1  // element is greater than middle element of array, so it will be in right half of array
            result == 0  -> return mid     // found the element
            result < 0   -> high = mid - 1 // element is less than middle element of array, so it will be in left half of the array.
        }
    }
    return -1
}

fun IntArray.binarySearch(element: Int) = binarySearch(
        min = 0,
        max = size - 1,
        comparison = { index -> element.compareTo(this[index]) }
)

[Trevor Hackman]

There already is a binarySearch function in stdlib so not sure about introducing a new one. And that code doesn't seem complete for this purpose.

If you do write your own binarySearch function in your project you have full access to use the index for comparison if needed, but you don't with the binarySearch function in stdlib which is why I think binarySearchIndexed would be good to have so that people don't need to write their own binary search boilerplate.

[Trevor Hackman]

Why shouldn't binarySearchIndexed exist when forEachIndexed, mapIndexed, reduceIndexed, foldIndexed, foldRightIndexed, filterIndexed, scanIndexed, etc. all exist?

[Derek Peirce]

Why doesn't it seem complete for your purpose? What exactly are you trying to do? And binarySearch takes a Comparator argument, which has a specific purpose of comparing two objects which should not depend on their indices. Meanwhile, the other methods you've listed are general-purpose with no specific semantic for what they need to do, so many use cases appear in which the index as an argument is useful.

[Trevor Hackman]

You're just searching on an IntArray, not on List<T> and just for some element, not with indexes. I'm not sure what at all you're trying to do.

[Derek Peirce]

Swapping out the IntArray for List<T> is trivial. What does your method look like?

[Trevor Hackman]

As in original post

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

[Derek Peirce]

Implementation-wise, I should clarify.

[Trevor Hackman]

The implementation is trivial, goal is to match the already existing binarySearch but add index to comparison.

/**
 * 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.
 *
 * @param 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.
 * @sample samples.collections.Collections.Lists.binarySearchWithComparisonFunction
 */
public fun <T> List<T>.binarySearch(fromIndex: Int = 0, toIndex: Int = size, comparison: (T) -> Int): Int {
    rangeCheck(size, fromIndex, toIndex)

    var low = fromIndex
    var high = toIndex - 1

    while (low <= high) {
        val mid = (low + high).ushr(1) // safe from overflows
        val midVal = get(mid)
        val cmp = comparison(midVal)

        if (cmp < 0)
            low = mid + 1
        else if (cmp > 0)
            high = mid - 1
        else
            return mid // key found
    }
    return -(low + 1)  // key not found
}

[Derek Peirce]

And you just want an equivalent with the comparison(midVal) replaced with comparison(mid, midVal), correct?

[Derek Peirce]

Using my general binarySearch as a base, is this what you're looking for?

fun <T> List<T>.binarySearchIndexed(
    fromIndex: Int = 0,
    toIndex: Int = size,
    comparison: (T, Int) -> Int,
): Int = binarySearch(
        min = fromIndex,
        max = toIndex - 1,
        comparison = { index -> comparison(get(index), index) }
)

With this example call:

fun main() {
    println(listOf<Int>(1, 2, 3, 6, 8, 10, 11, 16, 20).binarySearchIndexed { element, index ->
        println("checking $element at $index");
        11.compareTo(element)
    })
}

which yields:

checking 8 at 4
checking 11 at 6
6

[Trevor Hackman]

Yes that's correct

[Trevor Hackman]

And currently, if you want to do an indexed binary search with the existing binarySearch you can do something like

list.mapIndexed { index, it -> it to index }.binarySearch { ... }

But you lose log time complexity because you had to do a linear time map.

[Derek Peirce]

You could create an immutable view of a list that treats it as indexed

[Trevor Hackman]

Maybe, or you could just write your own binary search function that doesn't have this problem and that wouldn't have any overhead.

[Trevor Hackman]

Or stdlib could have binarySearchIndexed added to it so people don't have to write their own implementations.

[Derek Peirce]

I think that binarySearchIndexed is still an obscure enough use case that it doesn't warrant being in stdlib, but the general case binarySearch with be used by the existing stdlib methods and also used to easily write your own binarySearchIndexed.