Каков наилучший способ поиска элемента в отсортированном списке в JavaScript?

Question

У меня есть упорядоченный список целых чисел, и я хотел бы найти их.

Какой самый быстрый способ сделать это?

Это самая быстрая работа? Или мы можем оптимизировать его, потому что он заказан?

Array.prototype.Contains = function(value) {
    for (var index = 0; index < this.length; index++) {
        if (value == this[index]) {
            return true;
        }
    }
    return false;
}

Спасибо

Answer 1

Попытка реализовать " бинарный поиск ":

Array.prototype.binarySearch = function(v) {

    /* ARRAY MUST BE SORTED */

    if ( !this.length ) { return false; }
    if ( this[0] === v ) { return true; }

    var i, mid,
        start = 0,
        end = this.length,
        c = false;

    while ( c = (i = this[mid = start+((end-start)>>1)]) !== v ) {

        i < v ? (start = mid) : (end = mid);

        if (start >= end - 1) { break; }

    }

    return !c;

};

Answer 2

Если список отсортирован, самый быстрый способ - это всегда бинарный поиск. Это верно для всех языков, если у вас есть упорядоченный список.

http://en.wikipedia.org/wiki/Binary_search_algorithm

Answer 3

Часто удобно возвращать индекс найденного элемента из отсортированного списка. Необязательный второй параметр определяет, будет ли возвращено логическое значение или индекс.

Array.prototype.biSearch= function(v, ret){
 var L= this.length, i= -1, m;
 while(L - i> 1){
  if(this[m= L + i>> 1]< v) i= m;
  else L= m;
 }
 if(ret) return this[L]== v? L: -1;
 return this[L]== v;
}

Практически один и тот же код можно использовать для другой общей задачи - добавления элемента в отсортированный массив без необходимости повторной сортировки всего массива.

Если второй параметр не отправлен, элемент будет вставлен, только если он еще не существует в массиве.

Array.prototype.addtoSort= function(v, dup){
 var L= this.length, i= -1, m;
 while(L - i> 1){
  if(this[m= L + i>> 1]< v) i= m;
  else L= m;
 }
 if(this[L]!= v || dup){
  return this.splice(L,0,v);
 }
 return this.length;
}