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 w

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) [0] https://en.wikipedia.org/wiki/Interpolation_search https://en.wikipedia.org/wiki/Interpolation_search