/**
   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');
}