I might be missing something, but is there any way...

# announcements

[ghedeon]

I might be missing something, but is there any way to binary search in a descending IntArray?
All I can see is IntArray.binarySearch but that's only for ascending. Arrays.binarySearch allows you to specify the comparator but only for the Array<T>, not for the IntArray. Seems like a dead end.

[Egor Trutenko]

Why don't you reverse it? Kotlin's IntArray.binarySearch internally calls Arrays.binarySearch defined for int[] anyways. Either you sort your array explicitly, or you box your values and call Arrays.binarySearch for Array<T> with comparator

[ghedeon]

Multiple reasons:
1. binary search takes logN and reversing is N, it's slower.
2. the index I'll find in a reversed array can't be used with the original input, I'd need to adjust it
3. There is no obvious reason why it's not possible to provide a custom comparator for IntArray. Can't think of blockers here.

[ghedeon]

Btw, by "box your values" in this context you mean create an Array<T> copy? That also looks redundant. Idk, it's a first time when I see that Array<Int> could be a better choice and I'm confused why.

[Ruckus]

It may simply be an oversight. You can ask in #C0B8Q383C.

[Ruckus]

Or just file an issue.

[hudsonb]

for 3, that'd mean auto boxing anyways right

[hudsonb]

arr.toList().asReversed().binarySearch(...) avoids the N reversing cost

[ghedeon]

I'm not sure about auto boxing. I can't see why would you need to do anything at all with the initial array in order to perform a search.

[ghedeon]

you're right about asReversed(), the nr.2 still apply, tho

[hudsonb]

Binary search finds an element in a sorted array. By default it's using the natural sort order.

[ghedeon]

I think that's obvious, what is used by default

[ghedeon]

that's why we've got overriden binary search methods in Arrays for other cases

[hudsonb]

arr.asList().binarySearch(n, Comparator { o1, o2 -> o2 - o1 })

[hudsonb]

That resolves 1 and 2

[ghedeon]

that's actually cool and cheaper than toTypedArray(). Thank you!

[hudsonb]

NP - you could get fancy and define it as an extension function on IntArray too of course:

fun IntArray.binarySearch(element: Int, comparator: Comparator<Int>)
    = asList().binarySearch(8, comparator)

[hudsonb]

whoops that should be element not 8

[hudsonb]

and then youve solved 3 😉

[ghedeon]

awesome. There is also a predefined Comparisons.reverseOrder() to make it cleaner. 😉

[hudsonb]

I thought there was, I looked for it real quick but didnt turn anyhting up so I just did it myself quick

[Dico]

You still have boxing there. Implementing binarySearch manually is very easy, just make an extension function accepting IntComparator which is Java's comparator for primitive ints.

[Dico]

Alternatively, make an inline version that uses a regular Kotlin lambda.