JavaScript most efficient function to find an item in an Array? and explain this tricky code

Question

What can be the most efficient way to find an item in an array, which is logical and understood by a web developer?

I came across this piece of code:

var inArray = function(a, b, c, d) {
 for (c in b) d |= b[c] === a;
 return !!d
};

It works fine. Can someone please explain me the code?
I also came across an exact same question that might make mine as a duplicate. But my real question lies in explanation of the above code and why bitwise operator has been used into it.
Also, can there be a way without any for loop, or iteration to get index of an item in an Array?

• Elias Van Ootegem: for...in on an Array? Awsome!? Positively revolting code IMHO
• Om Shankar: @EliasVanOotegem, Changed my question. Thanks

Answer 1

var inArray = function(a, b, c, d) {
 for (c in b) d |= b[c] === a;
 return !!d
};

That is some terrible code, and you should run away from it. Bitwise operators are completely unnecessary here, and c and d being parameters makes no sense at all (as Raymond Chen pointed out, the author of the code likely did it to safe space of declaring local variables -- the problem though is that if true is passed in for d the code is suddenly broken, and the extra parameters destroys any sense of understanding that glancing at the declaration would provide).

I'll explain the code, but first, here's a better option:

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

Note that this is dependent on the array being an actual array. You could use a for (k in arr) type loop to generalize it to all objects.

---

Anyway, on to the explanation:

for (c in b) d |= b[c] === a;

This means that for every key in b (stored in c), we will check if b[c] === a. In other words, we're doing a linear scan over the array and checking each element against a.

d |= val is a bitwise or. The bits that are high in val will be set high in d. This is easier to illustrate in languages where bits are more exposed than in JS, but a simple illustration of it:

10011011
01000001
--------
11011011

It's just OR'ing each individual bit with the same location bit in the other value.

The reason it's an abuse here is that it convolutes the code and it depends on weird implicit casts.

x === y returns a boolean. A boolean being used in a bitwise expression makes little sense. What's happening though is that the boolean is being converted to a non-zero value (probably 1).

Similarly, undefined is what d will be. This means that d will be cast to 0 for the bitwise stuff.

0 | 0 = 0, but 0 | 1 = 1. So basically it's a glorified:

for (c in b) d = (d || (b[c] === a));

As for !!x that is just used to cast something to a bool. !x will take x, implicitly cast it to a bool and then negate it. The extra ! will then negate that again. Thus, it's likely implicitly casting to a bool (!!x being true implies that x is at least loosely true (1, "string", etc), and !!x implies that x is at least loosely false (0, "", etc).

---

This answer offers a few more options. Note though that all of them are meant to fallback to the native indexOf that will almost certainly be faster than anything we can code in script-land.

• Raymond Chen: c and d being declared as parameters is a lazy way of declaring them as local variables with the added risk that if somebody calls with four parameters, the initial value of d will be wrong!
• Corbin: @RaymondChen Ah, I suppose that it why it was done. The author of that terrible little snippet was apparently determined to make it stupidly compact :). Never even occurred to me that they did it to save a few characters.

Answer 2

This code is pretty poorly written, and barely readable. I wouldn't qualify it as "awesome"...

Here's a rewritten version, hopefully more readable:

function inArray (aElt, aArray) {
 var key;
 var ret = false;
 for (key in aArray)
 ret = ret || (aArray[key] === aElt);
 return ret;
}

The for loop seems like the most natural way to do that. You could do it recursively but that doesn't feel like the easiest approach here.

• Corbin: That can be rewritten to be significantly more efficient in cases where the element exists in the array and is not the last element. Just return true when the element is found, otherwise, return false at the bottom of the function. That way the for loop short circuits when the element is found.
• Paul S.: This isn't true. x = 1; x |= 2; x; // 3. |= is a binary OR assignment operator, not a logical OR.
• Ilmari Karonen: @PaulS.: Yes, but === can only evaluate to true or false, which map to 1 and 0 as numbers. For that limited range of values, | and || are effectively identical (except for short-circuit evaluation).
• Om Shankar: The code that I had put was a one-liner var inArray = function(a,b,c,d){for(c in b)d|=b[c]===a;return!!d }; modified to look good by some mod just now. It being one-liner made me look at it as awesome may be
• Jonathan Protzenko: Sure, I was just trying to rewrite this in a more readable fashion. More efficient ways include exiting from the loop when the element is found, or simply relying on the built-in indexOf function.

Answer 3

What can be the most efficient way to find an item in an array, which is logical and understood by a web developer?

Either the native method, haystack.indexOf(needle) !== -1 or a looped method which returns as soon as it can

function inArray(needle, haystack) {
 var i = haystack.length;
 while (i) if (haystack[--i] === needle) return true;
 return false;
};

• Corbin: That's a very C style while loop. A for loop would be a lot more readable, though that is of course just opinion.
• Paul S.: @Corbin I don't think I've ever written in C. I just know while is very fast and n !== 0 == true
• Corbin: A for loop is essentially a while loop. Computers have no concept of a for loop (or even a while loop). A similarly constructed for loop, or even while (i > 0) is going to have identical performance (or perhaps so little difference that it is truly negligible by any comparison). I'm just being picky (and obnoxiously opinionated) though :-). Either way, +1.
• Paul S.: Computers don't have the concept, but compilers will usually optimise/compile while differently to for so you can sometimes squeeze a tiny bit more if you choose a while. You are right though, the difference is minimal. The question asks for the most efficient way and this should be it (that it matches my preference is just a coincidence).
• Om Shankar: @PaulS. In that case, bitwise operators are even more fast. so the one-liner that created this doubt could be the fastest. I also wanted a logical, understood by a web-developer Solution. Reason being, there are Web Devs like me who don't have a Computer Science background :)

Answer 4

You asked for a recursive version

var inArray = function(arr, needle, index) {
 index = index || 0;
 if (index >= arr.length)
 return false;
 return arr[index] === needle
 ? true
 : inArray(arr, needle, index + 1);
}
console.log(inArray([1,5,9], 9));

• James: change "contains" to "inArray"
• Om Shankar: +1 for this. I didn't need it, just wanted to check how it could be done following the theory "all iterations can be converted to recursion"