A search algorithm based on Binary search which tries to reduce the number of memory accesses.
If, on top of knowing that the input is sorted, we assume that it is distributed uniformally,
we can then use the first and last object in the range to try and predict where the item we
are looking for would be. This means that we would be doing less memory accesses.
The formula for the prediction is indexOf(min) + (needle - min)/(max - min) * (indexOf(max) - indexOf(min))
Preditive Search
A search algorithm based on Binary search which tries to reduce the number of memory accesses. If, on top of knowing that the input is sorted, we assume that it is distributed uniformally, we can then use the first and last object in the range to try and predict where the item we are looking for would be. This means that we would be doing less memory accesses.
The formula for the prediction is indexOf(min) + (needle - min)/(max - min) * (indexOf(max) - indexOf(min))