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. au.php.net/manual/en/function.array-search.php#93352 — Russell Dias
– Russell Dias, Commented May 13, 2010 at 10:49

Community · Accepted Answer · 2017-05-23 12:33:35Z

11

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

edited May 23, 2017 at 12:33

CommunityBot

11 silver badge

answered May 13, 2010 at 10:48

ThiefMaster

320k85 gold badges608 silver badges648 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

nc3b · Accepted Answer · 2010-05-13 10:49:07Z

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, 2010 at 10:49

nc3b

16.4k5 gold badges53 silver badges63 bronze badges

1 Comment

Jordan Arsenault Over a year ago

I know it doesn't but to be fair, the OP may have thought that PHP was maintaining a sort-order under-the-hood.

cletus · Accepted Answer · 2010-05-13 10:48:25Z

4

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.

answered May 13, 2010 at 10:48

cletus

627k169 gold badges922 silver badges945 bronze badges

Collectives™ on Stack Overflow

Does in_array() use a binary search algorithm?

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related