<html>
<head>
<title>Hi :)</title>
</head>
<body>
<textarea id="tbox" rows="20" cols="50">
results:
--------</textarea>
<script>
window.log = document.getElementById('tbox');
function l(msg) {
log.value += '\r\n' + msg;
}
function make_delta(dN) {
var power = 1;
var i = 0;
var delta = new Array(42);
for (var j = 0; j < 43; j++) { delta[j] = 0; }
l('delta len is : ' + dN);
while (i <= dN) {
var half = power;
power <<= 1;
var di = Math.floor( ((dN + half) / power) );
delta[i] = di;
i++;
}
return delta;
}
function ubs(target, key, delta) {
var i = delta[0] - 1;
var d = 0;
l('middle of target: ' + i);
while(d < 300) {
if (key == target[i]) {
return i;
} else if (delta[d] == 0) {
return -1;
} else {
if (key < target[i]) {
l(key + ' is less than ' + target[i] + ' : ' + i);
i -= Math.round(delta[++d]);
} else {
l(key + ' is bigger than ' + target[i] + ' : ' + i);
i += Math.floor(delta[++d]);
}
}
}
}
target = [91, 97, 99, 101, 127, 121, 96, 98];
del = make_delta(target.length);
key = 99;
l('\r\nthinking...\r\n-----------------');
l(key + ' at index: ' + ubs(target, key, del));
</script>
</body>
</html>