Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. <html>
  2. <head>
  3. <title>Hi :)</title>
  4. </head>
  5. <body>
  6. <textarea id="tbox" rows="20" cols="50">
  7. results:
  8. --------</textarea>
  9. <script>
  10. window.log = document.getElementById('tbox');
  11.  
  12. function l(msg) {
  13.     log.value += '\r\n' + msg;
  14. }
  15.  
  16. function make_delta(dN) {
  17.     var power = 1;
  18.     var i = 0;
  19.     var delta = new Array(42);
  20.     for (var j = 0; j < 43; j++) { delta[j] = 0; }
  21.    l('delta len is : ' + dN);
  22.  
  23.    while (i <= dN) {
  24.         var half = power;
  25.         power <<= 1;
  26.         var di = Math.floor( ((dN + half) / power) );
  27.         delta[i] = di;
  28.         i++;
  29.    }
  30.  
  31.    return delta;
  32. }
  33.  
  34. function ubs(target, key, delta) {
  35.     var i = delta[0] - 1;
  36.     var d = 0;
  37.     l('middle of target: ' + i);
  38.  
  39.     while(d < 300) {
  40.         if (key == target[i]) {
  41.             return i;
  42.         } else if (delta[d] == 0) {
  43.             return -1;
  44.         } else {
  45.             if (key < target[i]) {
  46.                 l(key + ' is less than ' + target[i] + ' : ' + i);
  47.                 i -= Math.round(delta[++d]);
  48.             } else {
  49.                 l(key + ' is bigger than ' + target[i] + ' : ' + i);
  50.                 i += Math.floor(delta[++d]);
  51.             }
  52.         }
  53.     }
  54. }
  55.  
  56.  
  57.  
  58. target = [91, 97, 99, 101, 127, 121, 96, 98];
  59. del = make_delta(target.length);
  60. key = 99;
  61. l('\r\nthinking...\r\n-----------------');
  62. l(key + ' at index: ' + ubs(target, key, del));
  63. </script>
  64. </body>
  65. </html>