66

Does indexOf simply walk through the array or does it do something that is faster? I know that this is implementation dependent but what does Chrome or Firefox do?

user1056805
  • 2,633
  • 5
  • 21
  • 19
  • 1
    You should probably go to a mailing list for developers of the implementations you care about and ask there. Since ECMAScript is Java—like, I would expect developers to leverage underlying platform–native methods where possible since most already have optimised functions for this. But that is just a guess. – RobG Oct 10 '13 at 04:40
  • 2
    Firefox implementation can be seen [here](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/indexOf?redirectlocale=en-US&redirectslug=JavaScript%2FReference%2FGlobal_Objects%2FArray%2FindexOf). @GameAlchemist Please control your frustration & channelize it to buttons like the `close` button at SO... – loxxy Oct 10 '13 at 04:48

3 Answers3

66

The most efficient way to find the first index matching a value in an unsorted array is to just walk through the list in order, which is O(n). MDN also has some hints:

Returns the first index at which a given element can be found in the array, or -1 if it is not present.

[...]

fromIndex

Default: 0 (Entire array is searched)
The index to start the search at. If the index is greater than or equal to the array's length, -1 is returned, which means the array will not be searched. If the provided index value is a negative number, it is taken as the offset from the end of the array. Note: if the provided index is negative, the array is still searched from front to back. If the calculated index is less than 0, then the whole array will be searched.

In case you're wondering, here's how WebKit implements it:

EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState* exec)
{
    // 15.4.4.14
    JSObject* thisObj = exec->hostThisValue().toThis(exec, StrictMode).toObject(exec);
    unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
    if (exec->hadException())
        return JSValue::encode(jsUndefined());

    unsigned index = argumentClampedIndexFromStartOrEnd(exec, 1, length);
    JSValue searchElement = exec->argument(0);
    for (; index < length; ++index) {
        JSValue e = getProperty(exec, thisObj, index);
        if (exec->hadException())
            return JSValue::encode(jsUndefined());
        if (!e)
            continue;
        if (JSValue::strictEqual(exec, searchElement, e))
            return JSValue::encode(jsNumber(index));
    }

    return JSValue::encode(jsNumber(-1));
}
Community
  • 1
  • 1
Brendan Long
  • 53,280
  • 21
  • 146
  • 188
  • 1
    thanks, so if I know that the array I'm working with is sorted, I'm better of using custom implementation of binary search as it has better complexity of `O(log(N))`? – Max Koretskyi Apr 14 '17 at 10:52
  • 4
    @Maximus It depends on the size of your array, but if it's large enough that this is significant then it's worth a try. I would benchmark it to make sure you're not making it slower by replacing a built-in (C++) function with a JavaScript function though (for small `N`, the less efficient algorithm in C++ will probably beat the more efficient algorithm in JavaScript). – Brendan Long Apr 14 '17 at 14:04
3

With no guarantees about the nature or order of items in an array, you cannot do better than O(n), so it would walk through the array. Even if it was to parallelise the actual search across CPUs (no idea if firefox or chrome do this, but they could), it does not change the time complexity with a finite number of CPUs.

triggerNZ
  • 4,221
  • 3
  • 28
  • 34
  • 3
    JS arrays are not regular arrays as the name implies, but actually hash maps. It would be possible to just create a second index for the values in addition to the keys, thus giving better time complexity on value lookup in exchange for memory usage. – j-pb Nov 22 '15 at 23:45
  • 1
    @Casey It's worth noting that JS arrays _are_ JS objects - just with integer keys and some additional methods. From the [Mozilla Array docs](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array#Description): "Arrays are list-like objects whose prototype has methods to perform traversal and mutation operations." You can see for yourself that arrays use key/value pairs by running `Object.keys(['a', 'b']);` and `Object.values(['a', 'b']);`. – Peter Henry Jan 18 '18 at 04:00
-1

In ECMA6, you have the Set(), and then you can do:

var obj = new Set();
obj.add(1);
obj.has(1) === true;
obj.has(2) === false;

The performance of has is O(1).

maletor
  • 7,072
  • 7
  • 42
  • 63
Matheus
  • 109
  • 4