A colleague asked about why there is no binary search method in PHP, but only the slow linear time array_search. I don’t have answer though, but someone suggest that you can do fast searching in a hash by flipping the array into a hash:

<?php // DON'T USE THIS FUNCTION, IT IS SLOW function flip_search($list, $key) { $res = array_flip($list); if (array_key_exists($key, $res)) { return $res[$key]; } return FALSE; } ?>

What’s the run time of this function? **Linear**, as there is no magic in doing the flipping, but has to go through the array entry one by one, and not to mention it is memory inefficient. So if you get a sorted array, use binary search; if your array is not sorted, use the build-in array_search

I set out to write a general binary search for PHP.

<?php /* * Parameters: * $a - The sort array. * $first - First index of the array to be searched (inclusive). * $last - Last index of the array to be searched (exclusive). * $key - The key to be searched for. * $compare - A user defined function for comparison. Same definition as the one in usort * * Return: * index of the search key if found, otherwise return (-insert_index - 1). * insert_index is the index of smallest element that is greater than $key or sizeof($a) if $key * is larger than all elements in the array. */ function binary_search(array $a, $first, $last, $key, $compare) { $lo = $first; $hi = $last - 1; while ($lo <= $hi) { $mid = (int)(($hi - $lo) / 2) + $lo; $cmp = call_user_func($compare, $a[$mid], $key); if ($cmp < 0) { $lo = $mid + 1; } elseif ($cmp > 0) { $hi = $mid - 1; } else { return $mid; } } return -($lo + 1); } ?>

To use it is pretty straight forward:

<?php function cmp($a, $b) { return ($a < $b) ? -1 : (($a > $b) ? 1 : 0); } $a = array(1,2,3,4,5,6); $idx = binary_search($a, 0, sizeof($a), 4, 'cmp'); ?>

Feel free to use the code if you need it.

Advertisements