Does in_array() use a binary search algorithm?

7

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?

morpheous

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. http://au.php.net/manual/en/function.array-search.php#93352

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

Answers

10

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

ThiefMaster

Posted 2010-05-13T10:46:41.187

Reputation: 235 242

5

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

nc3b

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

3

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.

cletus

Posted 2010-05-13T10:46:41.187

Reputation: 499 933