php二分法在IP地址查询中的应用

    $begin_ip = sprintf('%u', $begin_ip);
    $end_ip   = sprintf('%u', $end_ip);

    do {
        if ($end - $begin <= 18) {
            fseek($fp, $begin + 8);
            $info = array();
            $info[0] = implode('', unpack('S', fread($fp, 2)));
            $info[1] = implode('', unpack('S', fread($fp, 2)));
            $info[2] = implode('', unpack('S', fread($fp, 2)));
            $info[3] = implode('', unpack('S', fread($fp, 2)));
            $info[4] = implode('', unpack('S', fread($fp, 2)));
            return $info;
        }

        $middle_seek = ceil((($end - $begin) / 18) / 2) * 18 + $begin;

        fseek($fp, $middle_seek);
        $middle_ip = implode('', unpack('L', fread($fp, 4)));
        $middle_ip = sprintf('%u', $middle_ip);

        if ($ip >= $middle_ip) {
            $begin = $middle_seek;
        } else {
            $end = $middle_seek;
        }
    } while (true);
}

　　以上$fp为打开ip.dat的文件句柄，由于是循环检索，所以写在函数外面，免得每次检索都要打开一次文件，30W行数据二分法最多也只需要循环7次(2^7)左右即可找到准确的IP信息。之后本来还想将ip.dat放在内存中加快检索速度，后来发现，字符串定位函数的效率，根本和文件指针的偏移定位不是在一个数量级的，所以还是放弃使用内存来存放IP库。
　　这个实现，使IP检索效率提高了近百倍，只是一个简单的二分法的应用，从此算法在WEB应用中不重要的观念彻底打消了。其实要实现这个，我还请教了金狐，我一开始是请他帮我生成一个纯真格式的IP库，然后用Discuz的IP查询函数来检索，不过他不肯帮我，最后造就了我的这个实践和学习。有时候，求人不如求己。