What is the best way to search for an item in a sorted list in javascript?

Question

I have an ordered list of integers, and would like to search through them.

What is the fastest way to do this?

Is this the fastest it will work? Or can we optimise it because it is ordered?

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

Thanks

Answer 1

If the list is sorted, the fastest way is always a binary search. This is true in all languages, as long as you have an ordered list.

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

Answer 2

Tried implementing a "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 3

It is often handy to return the index of the found item from a sorted list. The optional second parameter determines if a boolean or index is returned.

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

Virtually the same code can be used for another common task-adding an item to a sorted array without having to re-sort the whole array.

If the second parameter is not sent, the item will only be inserted if it does not already exist in the array.

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