A Faster Array Search in php

Php does a very good job at creating predefined methods that are optimized by default. However, sometimes with a little extra effort on our parts we can optimize a procedure even more. On the table today: the in_array() method. It is a very useful array allowing the user to search an array for a given value. The problem arises when this array becomes very large and many values must be searched.

For those not familiar with different search or optimization methods…there are many out there. No, no I’m not going to leave it at that. The in_array function is a linear search or sequential search, meaning it starts at the top of the array and goes to the bottom checking for a match. See the issue? If I’m looking for a value that lives at the bottom of the array then I have to wait a good bit (well for a programmer’s perspective) for the search to complete. So what is a better solution? The binary search.

The binary search works almost exactly like the “High, Low” game. You ask whether the search value is in 2 sets of numbers and it will tell you higher or lower. This seems simple enough, but you must remember this small detail: the set must be in order. Otherwise, the search will get lost because it may hit a smaller number while searching in an upper set. The reality of this is that most over our data comes from SQL queries which means guess what? We can already put our data in order.

Here is the code in PHP:

function binarySearch($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;