(note that binary search is an example of computer scientists acknowledging the existence of practitioners: they won't go so far as to do a k-ary search, for that would require engineering a [necessarily ephemeral] suitable value of k, but they have demonstrated goodwill in stepping beyond the much-cheaper-to-prove 1-ary search.)
You're making me wonder if it would make sense to have k scale with r (where r the narrowed down range).
In practice binary search tends to perform better if we switch to linear search for small enough r, right? Kind of like how insertion sort is faster when r is less than 20-40 integers on modern hardware (this is assuming we're dealing with dense arrays in either scenario, obviously).
One could say that this is effectively switching from k = 2 to k = r at some threshold value. What if instead we increase k gradually as some proportion of r as the latter gets smaller, and sample in ascending order (Although I bet that even if it works, interpolation search is probably faster anyway)
(note that binary search is an example of computer scientists acknowledging the existence of practitioners: they won't go so far as to do a k-ary search, for that would require engineering a [necessarily ephemeral] suitable value of k, but they have demonstrated goodwill in stepping beyond the much-cheaper-to-prove 1-ary search.)