54 lines
1.6 KiB
Plaintext
54 lines
1.6 KiB
Plaintext
/**
|
|
Binary search, in Jsish, based on Javascript entry
|
|
Tectonics: jsish -u -time true -verbose true binarySearch.jsi
|
|
*/
|
|
function binarySearchIterative(haystack, needle) {
|
|
var mid, low = 0, high = haystack.length - 1;
|
|
|
|
while (low <= high) {
|
|
mid = Math.floor((low + high) / 2);
|
|
if (haystack[mid] > needle) {
|
|
high = mid - 1;
|
|
} else if (haystack[mid] < needle) {
|
|
low = mid + 1;
|
|
} else {
|
|
return mid;
|
|
}
|
|
}
|
|
return null;
|
|
}
|
|
|
|
/* recursive */
|
|
function binarySearchRecursive(haystack, needle, low, high) {
|
|
if (high < low) { return null; }
|
|
|
|
var mid = Math.floor((low + high) / 2);
|
|
|
|
if (haystack[mid] > needle) {
|
|
return binarySearchRecursive(haystack, needle, low, mid - 1);
|
|
}
|
|
if (haystack[mid] < needle) {
|
|
return binarySearchRecursive(haystack, needle, mid + 1, high);
|
|
}
|
|
return mid;
|
|
}
|
|
|
|
/* Testing and timing */
|
|
if (Interp.conf('unitTest') > 0) {
|
|
var arr = [];
|
|
for (var i = -5000; i <= 5000; i++) { arr.push(i); }
|
|
|
|
assert(arr.length == 10001);
|
|
assert(binarySearchIterative(arr, 0) == 5000);
|
|
assert(binarySearchRecursive(arr, 0, 0, arr.length - 1) == 5000);
|
|
|
|
assert(binarySearchIterative(arr, 5000) == 10000);
|
|
assert(binarySearchRecursive(arr, -5000, 0, arr.length - 1) == 0);
|
|
|
|
assert(binarySearchIterative(arr, -5001) == null);
|
|
|
|
puts('--Time 100 passes--');
|
|
puts('Iterative:', Util.times(function() { binarySearchIterative(arr, 42); }, 100), 'µs');
|
|
puts('Recursive:', Util.times(function() { binarySearchRecursive(arr, 42, 0, arr.length - 1); }, 100), 'µs');
|
|
}
|