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

admin管理员组

文章数量:1356716

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

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

• javascript
• arrays
• sorting

Share Improve this question Follow asked Dec 3, 2009 at 1:18 RussellRussell 17.7k2424 gold badges8383 silver badges127127 bronze badges 1

• 2 This is not a duplicate, as I am specifically asking about an ordered list. – Russell Commented Dec 3, 2009 at 1:26

Add a ment  | 

3 Answers 3

Sorted by: Reset to default 7

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;

};

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/wiki/Binary_search_algorithm

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

本文标签： arraysWhat is the best way to search for an item in a sorted list in javascriptStack Overflow