二分查找包含负值的数组

Question

function BinarySearch(items, value) {
    var start = 0,
    stop = items.length - 1,
    mid = Math.floor((stop + start) / 2);

    while (items[mid] !== value && start < stop) {
        if (value < items[mid]) {
           stop = mid - 1;
        } else if (value > items[mid]) {
           start = mid + 1;
        }
       mid = Math.floor((stop + start) / 2);
    }
    var output = (items[mid] != value) ? -1 : mid;
    return output;
}

var arr = [5, 6, 7, 8, 9, 10, 1, -1, 2, 3];
var key = -1;
var ans = BinarySearch(arr, key);
console.log("ans is " + ans);

我试图找到 - 1，使用二分搜索，但它给出了不正确的结果。如果所有数组元素都是正数，则效果很好，但如果数组元素包含元素值并且我们尝试找到负值，它会给出错误的结果。

Answer 1

二分查找的工作时间是对数。 O(logn) 满足此属性是因为二分查找仅适用于排序数组（并且移位条件根据升序和降序顺序而变化）。 您的输入数组未排序。