49 lines
1.0 KiB
HTML
49 lines
1.0 KiB
HTML
<script src="../resources/magnitude-perf.js"></script>
|
|
<script>
|
|
function setupFunction(magnitude)
|
|
{
|
|
array = [];
|
|
for (var i = 0; i < magnitude; i++) {
|
|
array[i] = i;
|
|
}
|
|
}
|
|
|
|
function binarySearch(arry, val) {
|
|
if (!arry.length)
|
|
return -1;
|
|
return help(arry, val, 0, arry.length - 1);
|
|
}
|
|
|
|
function help(arry, val, start, end) {
|
|
if (end == start) {
|
|
if (arry[end] == val)
|
|
return end;
|
|
else
|
|
return -1;
|
|
}
|
|
|
|
var index = start + Math.floor((end - start) / 2);
|
|
if (arry[index] == val)
|
|
return index;
|
|
|
|
if (arry[index] > val) {
|
|
if (index == start)
|
|
return -1;
|
|
return arguments.callee(arry, val, start, index - 1);
|
|
}
|
|
|
|
if (index == end)
|
|
return -1;
|
|
|
|
return arguments.callee(arry, val, index + 1, end);
|
|
}
|
|
|
|
function test(magnitude)
|
|
{
|
|
binarySearch(array, 0);
|
|
}
|
|
|
|
Magnitude.description("Tests that binary search over an array is logarithmic.");
|
|
Magnitude.run(setupFunction, test, Magnitude.LOGARITHMIC);
|
|
</script>
|