确定元素是否在已排序数组中的最快方法

Question

我有一个包含1000个或更多值（最多可达5000个以上）的已排序整数数组。我需要编写一个函数，该函数接收一个整数并基于该元素是否在数组中返回一个布尔值。我知道可以使用for循环和break来编写，也知道可以使用jquery .InArray来实现。

在这种已排序的情况下，最好的实现方式是什么？

谢谢。

- frenchie

Answer 1

如果知道数组是有序的，二分查找将是最佳方法。

- g.d.d.c

---

http://www.nczonline.net/blog/2009/09/01/computer-science-in-javascript-binary-search/ - Pete

Answer 2

我认为你应该使用二分查找算法。 二分查找算法的时间复杂度为，而线性查找算法的平均时间复杂度为。

选择适合你的变体吧。这里有一篇文章提供了一个例子：链接。

function binarySearch(items, value){

    var startIndex  = 0,
        stopIndex   = items.length - 1,
        middle      = Math.floor((stopIndex + startIndex)/2);

    while(items[middle] != value && startIndex < stopIndex){

        //adjust search area
        if (value < items[middle]){
            stopIndex = middle - 1;
        } else if (value > items[middle]){
            startIndex = middle + 1;
        }

        //recalculate middle
        middle = Math.floor((stopIndex + startIndex)/2);
    }

    //make sure it's the right value
    return (items[middle] != value) ? -1 : middle;
}

或者这个看起来更简单的版本来自这篇文章，其中包含了许多不同语言的二分搜索函数。

function binary_search_iterative(a, value) {
    var lo = 0, hi = a.length - 1, mid;
    while (lo <= hi) {
        mid = Math.floor((lo+hi)/2);
        if (a[mid] > value)
            hi = mid - 1;
        else if (a[mid] < value)
            lo = mid + 1;
        else
            return mid;
    }
    return null;
}

Google Closure中也有二分查找，代码在这里。

而且，在维基百科上有关于二分查找算法如何工作的良好描述（链接）。

- jfriend00

Answer 3

如果数组已经排序，则答案也是排序的-使用二分查找。

- Martin James

Answer 4

如果需要进行多次查找，请迁移到类似于映射的对象。

var fastLookup = {};
mySortedArray.forEach(function(i){fastLookup[i]=true)});

//Each time:
  if (fastLookup[key]===true){ //do thing
  }

- user1212212

Answer 5

许多编程语言已经实现了这一点，例如在Java中，您可以使用Collections.binarySearch(List> list, T key)方法，我相信C#也有某种形式的BinarySearch方法。

- Merf