Returntype of searchsorted* should always be the keytype

[sostock]

Currently, the type of the index returned by the find* and searchsorted* functions is kind of inconsistent:

• findfirst etc. (almost) always returns an Int (unless it returns nothing).
• the return value searchsortedfirst(vec, x) depends on the type of x:

  julia> typeof(searchsortedfirst(1:5, 2))
  Int64
  
  julia> typeof(searchsortedfirst(1:5, big(2)))
  BigInt

The different return types make it harder to write type-stable code. For example, I am writing a function that returns an index of a sorted array, using findlast in one branch of the function and searchsortedlast in another.

Another problem with the find* behavior is that it errors when the indices of the array are not representable as Ints (but this is a separate issue that should be fixed in keys or LinearIndices, cf. #32566)

My proposal: The type returned by find* and searchsorted* should only depend on the type of the collection that is being searched. In my opinion, the obvious choice for that type would be eltype(eachindex(collection)).

[StefanKarpinski]

Agree that it seems broken for the type of the value being searched for to affect the type of the index returned.

[mbauman]

Yes, this needs to be fixed. Note that this only affects ranges — they do math against the value to compute the result, but we need to convert things back to the correct index type. It should be as easy as throwing a ::keytype(r) return type assertion on the relevant functions.

[sostock]

In addition to the searchsorted* functions, findnext and findprev are also affected. The returntype of findnext([f,] A, start)/findprev([f,] A, start) depends on the type and value of start:

julia> typeof(findnext(iseven, 1:5, big(1)))
Int64

julia> typeof(findnext(iseven, 1:5, big(2)))
BigInt

Should this be fixed as well, or can it be ignored (since most people will probably use an Int for start anyway)?

[mbauman]

Yes, that'd be good to fix at the same time.