I might be missing something but is there any way to binary

Question

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 lt T gt ` not for the `IntArray` Seems like a dead end

Egor Trutenko · Answer

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 lt T gt ` with comparator

ghedeon · Answer

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 · Answer

Btw by box your values in this context you mean create an `Array lt T gt ` copy That also looks redundant Idk it s a first time when I see that `Array lt Int gt ` could be a better choice and I m confused why

Ruckus · Answer

It may simply be an oversight You can ask in < C0B8Q383C|stdlib>

Ruckus · Answer

Or just file an issue

hudsonb · Answer

for 3 that d mean auto boxing anyways right

hudsonb · Answer

`arr toList asReversed binarySearch ` avoids the N reversing cost

ghedeon · Answer

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 · Answer

you re right about `asReversed ` the nr 2 still apply tho

hudsonb · Answer

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

ghedeon · Answer

I think that s obvious what is used by default

ghedeon · Answer

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

hudsonb · Answer

`arr asList binarySearch n Comparator o1 o2 gt o2 o1 `

hudsonb · Answer

That resolves 1 and 2

ghedeon · Answer

that s actually cool and cheaper than `toTypedArray ` Thank you

hudsonb · Answer

NP you could get fancy and define it as an extension function on IntArray too of course ``` fun IntArray binarySearch element Int comparator Comparator lt Int gt = asList binarySearch 8 comparator ```

hudsonb · Answer

whoops that should be `element` not `8`

hudsonb · Answer

and then youve solved 3 wink

ghedeon · Answer

awesome There is also a predefined `Comparisons reverseOrder ` to make it cleaner wink

hudsonb · Answer

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

Dico · Answer

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 · Answer

Alternatively make an inline version that uses a regular Kotlin lambda