expand and reduce search:
start with the bias
value (guess
, last
), expand the search range step-by-step to find the nearest low
and high
values (low < actual < high
), then reduce the search range to find the actual
value
here an implementation in javascript (sorry for not being theoretical) (even less theoretical: a benchmark)
function binarySearchBiased(haystack, needle, comparator, state) {
// find nearest low and high values = expand search range
let cmp = comparator(haystack[state.last], needle);
if (cmp == 0) return state.last;
function found(val) { state.last = val; return val }
let low, high;
const max_high = haystack.length - 1;
if (cmp > 0) { // item > needle
high = state.last;
// find nearest low value
for (let diff = 1; ; diff *= 2) {
low = high - diff;
if (low < 0) { low = 0; break }
let cmp = comparator(haystack[low], needle);
if (cmp == 0) return found(low);
if (cmp < 0) break; // item < needle
high = low - 1; // exclude low from range
}
}
else { // item < needle
low = state.last;
// find nearest high value
for (let diff = 1; ; diff *= 2) {
high = low + diff;
if (high > max_high) { high = max_high; break }
let cmp = comparator(haystack[high], needle);
if (cmp == 0) return found(high);
if (cmp > 0) break; // item > needle
low = high + 1; // exclude high from range
}
}
// binary search = reduce search range
while (low <= high) {
const mid = low + ((high - low) >> 1);
const cmp = comparator(haystack[mid], needle);
if (cmp == 0) return found(mid);
if (cmp < 0) { low = mid + 1 }
else { high = mid - 1 }
}
return -1; // not found
}
function compare(item, needle) {
return item - needle;
}
search_state = { last: 0 };
binarySearchBiased(haystack, needle, compare, search_state);
this is (obviously) optimized for 'sequential search' where last_needle and current_needle are very similar, aka 'neighbor search'