Sunday, June 3, 2012

Best way to find an item in a JavaScript array?



Possible Duplicate:

array.contains(obj) in JavaScript




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


Source: Tips4all

9 comments:

  1. function include(arr,obj) {
    return (arr.indexOf(obj) != -1);
    }


    EDIT:
    This will not work on IE6 though. The best workaround is to define it yourself if it's not present:


    Mozilla's (ECMA-262) version:

    if (!Array.prototype.indexOf)
    {

    Array.prototype.indexOf = function(searchElement /*, fromIndex */)

    {


    "use strict";

    if (this === void 0 || this === null)
    throw new TypeError();

    var t = Object(this);
    var len = t.length >>> 0;
    if (len === 0)
    return -1;

    var n = 0;
    if (arguments.length > 0)
    {
    n = Number(arguments[1]);
    if (n !== n)
    n = 0;
    else if (n !== 0 && n !== (1 / 0) && n !== -(1 / 0))
    n = (n > 0 || -1) * Math.floor(Math.abs(n));
    }

    if (n >= len)
    return -1;

    var k = n >= 0
    ? n
    : Math.max(len - Math.abs(n), 0);

    for (; k < len; k++)
    {
    if (k in t && t[k] === searchElement)
    return k;
    }
    return -1;
    };

    }

    Daniel James's version:

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

    roosteronacid's version:

    Array.prototype.hasObject = (
    !Array.indexOf ? function (o)
    {
    var l = this.length + 1;
    while (l -= 1)
    {
    if (this[l - 1] === o)
    {
    return true;
    }
    }
    return false;
    } : function (o)
    {
    return (this.indexOf(o) !== -1);
    }
    );

    ReplyDelete
  2. If you are using jQuery:

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

    ReplyDelete
  3. First, implement indexOf in JavaScript for browsers 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.

    ReplyDelete
  4. 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:


    Pick the middle element of the array.
    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.
    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.

    ReplyDelete
  5. 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...

    ReplyDelete
  6. 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

    ReplyDelete
  7. It depends on your purpose. If you program for the Web, avoid indexOf, it isn't supported by Internet Explorer 6 (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 it is faster than anything you can do in JavaScript (except binary search/dichotomy if the array is appropriate).
    Note: it is a question of taste, but I would do a return false; at the end of your routine, to return a true Boolean...

    ReplyDelete
  8. A robust way to check if an object is an array in javascript is detailed here:

    Here are two functions from the xa.js framework which I attach to a utils = {} ‘container’. These should help you properly detect arrays.

    var utils = {};

    /**
    * utils.isArray
    *
    * Best guess if object is an array.
    */
    utils.isArray = function(obj) {
    // do an instanceof check first
    if (obj instanceof Array) {
    return true;
    }
    // then check for obvious falses
    if (typeof obj !== 'object') {
    return false;
    }
    if (utils.type(obj) === 'array') {
    return true;
    }
    return false;
    };

    /**
    * utils.type
    *
    * Attempt to ascertain actual object type.
    */
    utils.type = function(obj) {
    if (obj === null || typeof obj === 'undefined') {
    return String (obj);
    }
    return Object.prototype.toString.call(obj)
    .replace(/\[object ([a-zA-Z]+)\]/, '$1').toLowerCase();
    };


    If you then want to check if an object is in an array, I would also include this code:

    /**
    * Adding hasOwnProperty method if needed.
    */
    if (typeof Object.prototype.hasOwnProperty !== 'function') {
    Object.prototype.hasOwnProperty = function (prop) {
    var type = utils.type(this);
    type = type.charAt(0).toUpperCase() + type.substr(1);
    return this[prop] !== undefined
    && this[prop] !== window[type].prototype[prop];
    };
    }


    And finally this in_array function:

    function in_array (needle, haystack, strict) {
    var key;

    if (strict) {
    for (key in haystack) {
    if (!haystack.hasOwnProperty[key]) continue;

    if (haystack[key] === needle) {
    return true;
    }
    }
    } else {
    for (key in haystack) {
    if (!haystack.hasOwnProperty[key]) continue;

    if (haystack[key] == needle) {
    return true;
    }
    }
    }

    return false;
    }

    ReplyDelete
  9. assuming .indexOf() is implemented can implement something similar to obj.hasOwnProperty(prop)

    Object.defineProperty( Array.prototype,'has',
    {
    value:function(o){return this.indexOf(o)!=-1},
    writable:false,
    enumerable:false
    }
    )


    now the new method can be used like

    [22 ,'a', {prop:'x'}].has(12)


    returning false

    ReplyDelete