Does in_array() use a binary search algorithm?

Question

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?

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, May 13 '10 at 10:49

score 11 · Accepted Answer · edited May 23 '17 at 12:33

11

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

edited May 23 '17 at 12:33

Community

1
1

answered May 13 '10 at 10:48

ThiefMaster

298,938
77
579
623

score 5 · Answer 2 · answered May 13 '10 at 10:49

5

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

answered May 13 '10 at 10:49

nc3b

14,524
5
49
63

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 May 29 '13 at 05:32

score 4 · Answer 3 · answered May 13 '10 at 10:48

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.

Does in_array() use a binary search algorithm?

3 Answers3