Каков наилучший способ поиска элемента в отсортированном списке в 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

Пробовал, реализующего «binary search»:

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; 
}