LayoutTests/perf/array-binary-search.html

   1 <script src="../resources/magnitude-perf.js"></script>
   2 <script>
   3 function setupFunction(magnitude)
   4 {
   5     array = [];
   6     for (var i = 0; i < magnitude; i++) {
   7         array[i] = i;
   8     }
   9 }
  10
  11 function binarySearch(arry, val) {
  12     if (!arry.length)
  13         return -1;
  14     return help(arry, val, 0, arry.length - 1);
  15 }
  16
  17 function help(arry, val, start, end) {
  18     if (end == start) {
  19         if (arry[end] == val)
  20             return end;
  21         else
  22             return -1;
  23     }
  24
  25     var index = start + Math.floor((end - start) / 2);
  26     if (arry[index] == val)
  27         return index;
  28
  29     if (arry[index] > val) {
  30         if (index == start)
  31             return -1;
  32         return arguments.callee(arry, val, start, index - 1);
  33     }
  34
  35     if (index == end)
  36         return -1;
  37
  38     return arguments.callee(arry, val, index + 1, end);
  39 }
  40
  41 function test(magnitude)
  42 {
  43     binarySearch(array, 5);
  44 }
  45
  46 Magnitude.description("Tests that binary search over an array is logarithmic.");
  47 Magnitude.run(setupFunction, test, Magnitude.LOGARITHMIC);
  48 </script>