Does in_array() use a binary search algorithm?


I have a largish array of string that I want to use as a look-up.

I am using in_array(), but I suspect its doing a simple loop through - does anyone know whether the in_array() algo uses a bsearch algo?


Posted 2010-05-13T10:46:41.187

Reputation: 6 082

Not sure if in_array does. I came across this, thought you might find it handy.

– Russell Dias – 2010-05-13T10:49:29.547



in_array() is O(n). Also see List of Big-O for PHP functions


Posted 2010-05-13T10:46:41.187

Reputation: 235 242


Since it doesn't require the array to be sorted, I don't see how it could do a binary search.


Posted 2010-05-13T10:46:41.187

Reputation: 10 463

I know it doesn't but to be fair, the OP may have thought that PHP was maintaining a sort-order under-the-hood. – Jordan Arseno – 2013-05-29T05:32:56.997


in_array() uses a linear (O(n)) search rather than a binary (O(log n)) search.

If you want O(log n) or better I would suggest you either put the values you want to search as the keys in an array or you create an index structure that effectively does the same thing.


Posted 2010-05-13T10:46:41.187

Reputation: 499 933