All purpose binary search in PHP

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.

Adding ping() function to PDO

Recently helped my colleague to add the missing mysqli_ping() function to PDO object in PHP. If anyone missed it, here it is:

class NPDO {
    private $pdo;
    private $params;

    public function __construct() {
        $this->params = func_get_args();
        $this->init();
    }

    public function __call($name, array $args) {
        return call_user_func_array(array($this->pdo, $name), $args);
    }

    // The ping() will try to reconnect once if connection lost.
    public function ping() {
        try {
            $this->pdo->query('SELECT 1');
        } catch (PDOException $e) {
            $this->init();            // Don't catch exception here, so that re-connect fail will throw exception
        }

        return true;
    }

    private function init() {
        $class = new ReflectionClass('PDO');
        $this->pdo = $class->newInstanceArgs($this->params);
    }
}