一道面试题:从数组取IP对应地址

2009-08-13 09:38:59 作者：allniu 来源：www.allniu.com 浏览次数：0 网友评论 0 条

IP数据库存放在一个php文件中,格式形如:

<?php

$ip[0]->start=“058016000000″;

$ip[0]->end=“058016255255″;

$ip[0]->area=“贵州”;

$ip[1]->start=“058017000000″;

$ip[1]->end=“058017127255″;

$ip[1]->area=“江西”;

$ip[2]->start=“058017128000″;

$ip[2]->end=“058017255255″;

$ip[2]->area=“重庆”;

$ip[3]->start=“058018000000″;

$ip[3]->end=“058018255255″;

$ip[3]->area=“内蒙古”;

$ip[4]->start=“058019000000″;

$ip[4]->end=“058019255255″;

$ip[4]->area=“湖北”;

…..

?>

思路：一个明显的2分法查找；当然用上递归…解决代码如下：

<?php
/**************************
@Filename: getadd.php
@Version : 0.0.1
@Author  : simplephp@163.com
@Update  :
@Content :
**************************/

include(”ip.php”);

$start=0;
$end=count($ip);

echo getadd(”058016000003″,$start,$end);

function getadd($key,$start,$end)
{
global $ip;

//中间值
$mid_len=intval(($end-$start)/2);

if($key>$ip[$start+$mid_len]->end)
{
$start=$start+$mid_len;
}
elseif($key<$ip[$start+$mid_len]->start)
{
$end=$end-$mid_len;
}
elseif($key>$ip[$start+$mid_len]->start&&$key<$ip[$start+$mid_len]->end)
{
return $ip[$start+$mid_len]->area;
}

$add=getadd($key,$start,$end);
return $add;
}

?>