Skip to content

Instantly share code, notes, and snippets.

@thisboyiscrazy
Last active August 29, 2015 13:55
Show Gist options
  • Save thisboyiscrazy/8713496 to your computer and use it in GitHub Desktop.
Save thisboyiscrazy/8713496 to your computer and use it in GitHub Desktop.
Binary search the return value of f for the closest value v is between starting with min going to max.
var searchHighLow = function(v,f,min,max) {
var t, dat;
for (;;) {
dat = f(min);
if(dat === v) return [min,min];
t = (min + max) >> 1;
dat = f(t);
if(dat === v) return [t,t];
if(dat < v) min = t;
dat = f(max);
if(dat === v) return [max,max];
t = (min + max) >> 1;
dat = f(t);
if(dat === v) return [t,t];
if(dat > v) max = t;
if((max - min) < 17) {
var tmin = min, tmax = max
dat = f(tmin);
if(dat > v) {
tmin = undefined;
} else {
t = tmin;
while(t <= max && (dat = f(t)) <= v ) {
if(dat === v) return [t,t];
tmin = t
t++;
};
}
dat = f(tmax);
if(dat < v) {
tmax = undefined;
} else {
t = tmax;
while(t >= min && (dat = f(t)) >= v ) {
if(dat === v) return [t,t];
tmax = t;
t--;
};
}
return [tmin,tmax];
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment