binary in_array search

Question

I use a lot of in_array functions and it seems to bog down my loading times. I found the following code in the in_array php documentation. The writer states "this function is five times faster than in_array(). It uses a binary search and should be able to be used as a direct replacement."

function fast_in_array($elem, $array) 
{
   $top = sizeof($array) -1;
   $bot = 0;
   while($top >= $bot) 
   {
      $p = floor(($top + $bot) / 2);
      if ($array[$p] < $elem) $bot = $p + 1;
      elseif ($array[$p] > $elem) $top = $p - 1;
      else return TRUE;
   }
   return FALSE;
}

However the function works, but only half of the time, sometimes it doesnt output everything it should be outputting for example if I have an array with apples, oranges, and lemons, and do an match for apples and oranges it will only print oranges or something weird. Could someone please explain to me what exactly this script does, and why it doesn't work as a substitute for in_array.

One reason it doesn't work is because PHP comparisons are broken for heterogeneous datatypes. What data are you storing in the array exactly? — Antimony
– Antimony, Commented Aug 7, 2012 at 23:51
Well for example, when i tested this code I was matching allowed or 'editable' row columns with queried columns. bit difficult to explain. but needless to say its not sorted. — Alex
– Alex, Commented Aug 7, 2012 at 23:53
it would be even faster if you flip the array and use array_key_exists instead (array_fill_keys($yourarray,1)). keep in mind that this will only work if the elements are unique though. edit: values have to be scalar too. — mpen
– mpen, Commented Aug 7, 2012 at 23:55

Antimony · Accepted Answer · 2012-08-07 23:52:25Z

11

It performs a binary search, which assumes the array is in sorted total order. If the array is not sorted, it will fail.

answered Aug 7, 2012 at 23:52

Antimony

39.8k13 gold badges103 silver badges115 bronze badges

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

3 Comments

Alex Over a year ago

so basically since the data comes in unsorted, and since that would require more processing, this will not be in any shape or form 'faster'

mpen Over a year ago

@Alex: that depends. sorting takes O(n log n) time, then a binary search takes O(log n) time. vs regular in_array which takes O(n) time...so..yeah, you're right. unless you're performing multiple searches and only one sort, plain old in_array is better than sort+binary search.

Antimony Over a year ago

Also, if the array has heterogeneous data, it can't be sorted reliably in the first place.

Pawin Vongmasa · Accepted Answer · 2012-08-07 23:53:34Z

5

This function does binary search. It only works if the array is sorted.

P.S. The claim that it works "five times faster" is pretty funny.

answered Aug 7, 2012 at 23:53

Pawin Vongmasa

911 bronze badge

1 Comment

Alex Over a year ago

yea i thought so too, but i decided to give it a whirl

Collectives™ on Stack Overflow

binary in_array search

2 Answers 2

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related