Best way to find an item in a JavaScript Array ?

Question

What is the best way to find if an object is in an array ?

This is the best way I know:

function include(arr, obj) {
  for(var i=0; i<arr.length; i++) {
    if (arr[i] == obj) return true;
  }
}

include([1,2,3,4], 3); // true
include([1,2,3,4], 6); // undefined

Answer 1

If the array is unsorted, there isn't really a better way (aside from using the above-mentioned indexOf, which I think amounts to the same thing). If the array is sorted, you can do a binary search, which works like this:

1. Pick the middle element of the array.
2. Is the element you're looking for bigger than the element you picked? If so, you've eliminated the bottom half of the array. If it isn't, you've eliminated the top half.
3. Pick the middle element of the remaining half of the array, and continue as in step 2, eliminating halves of the remaining array. Eventually you'll either find your element or have no array left to look through.

Binary search runs in time proportional to the logarithm of the length of the array, so it can be much faster than looking at each individual element.

Answer 2

Here's some meta-knowledge for you - if you want to know what you can do with an Array, check the documentation - here's the Array page for Mozilla

http://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Global_Objects/Array

There you'll see reference to indexOf, added in Javascript 1.6

Answer 3

It depends on your purpose. If you program for the Web, avoid indexOf, it isn't supported by IE6 (lot of them still used!), or do conditional use:

if (yourArray.indexOf !== undefined) result = yourArray.indexOf(target);
else result = customSlowerSearch(yourArray, target);

indexOf is probably coded in native code, so faster than anything you can do in JS (except binary search/dichotomy if the array is appropriate). Note: question of taste, but I would do a return false; at the end of your routine, to return a true boolean...

Answer 4

First, implement indexOf in javascript for browser's that don't already have it, for example see Erik Arvidsson's array extras (also, the associated blog post). And then you can use indexOf without worrying about browser support. Here's a slightly optimised version of his indexOf implementation:

if (!Array.prototype.indexOf) {
    Array.prototype.indexOf = function (obj, fromIndex) {
        if (fromIndex == null) {
            fromIndex = 0;
        } else if (fromIndex < 0) {
            fromIndex = Math.max(0, this.length + fromIndex);
        }
        for (var i = fromIndex, j = this.length; i < j; i++) {
            if (this[i] === obj)
                return i;
        }
        return -1;
    };
}

It's changed to store the length so that it doesn't need to look it up every iteration. But the difference isn't huge. A less general purpose function might be faster:

var include = Array.prototype.indexOf ?
    function(arr, obj) { return arr.indexOf(obj) !== -1; } :
    function(arr, obj) {
        for(var i = -1, j = arr.length; ++i < j;)
            if(arr[i] === obj) return true;
        return false;
    };

I prefer using the standard function and leaving this sort of micro-optimization for when it's really needed. But if you're keen on micro-optimization I adapted the benchmarks that roosterononacid linked to in the comments, to benchmark searching in arrays. They're pretty crude though, a full investigation would test arrays with different types, different lengths and finding objects that occur in different places.

Answer 5

If you are using jQuery:

http://api.jquery.com/jQuery.inArray/

Answer 6

Here's a flexible approach to searching arrays of objects using whichever object property or properties you desire: link text

I've just used it myself :)

Enjoy...

Answer 7

For some reason I was getting a js error (in both Firefox 3.6.6 and IE 7 using the for loop construct in Daniel's sample:

for (var i = fromIndex, j = this.length; i < j; i++) {
        if (this[i] === obj)
            return i;
    }

I changed it to evaluate the array length outside the loop beforehand:

 var len = this.length;
 for (var i = fromIndex; i < j; i++) {
            if (this[i] === obj)
            return i;
 }

and then it worked.

Anyone know why I would get an error?

Answer 8

New Document

var arr=new Array(5); for(var da=0;da

//how can i searchwhether an elemnt is there in the given list or not using flag.