静态查找
- 顺序查找
/**
* Common search
*
* @param array $arr
* @param mixed $item
*
* @return int
*/
public function search(array $arr, $item)
{
for ($i = 0; $i < count($arr); $i++) {
if ($arr[$i] == $item) {
return $i;
}
}
return -1;
}
- 折半查找
/**
* Binary search
*
* @param array $arr
* @param mixed $item
*
* @return int
*/
public function binSearch(array $arr, $item)
{
if (empty($arr)) {
return -1;
}
$low = 0;
$high = count($arr) - 1;
while ($low <= $high) {
//$mid = intval(($high + $low) / 2) 可能溢出
$mid = intval(($high - $low) / 2) + $low;
$val = $arr[$mid];
if($item == $arr) {
return $mid;
} elseif ($item < $val) {
$high = $mid -1;
} else {
$low = $mid + 1;
}
}
return -1;
}
- 递归折半查找
/**
* Recursion search
*
* @param array $arr
* @param mixed $item
* @param int $low
* @param int $high
*
* @return int
*/
public function binRecSearch(array $arr, $item, $low, $high){
if (empty($arr) || $low > $high || $low < 0) {
return -1;
}
$low = 0;
$high = count($arr) - 1;
if ($low <= $high) {
$mid = intval(($high - $low) / 2) + $low;
if ($item == $arr[$mid]) {
return $mid;
} elseif ($item < $arr[$mid]) {
return binRecSearch($arr, $item, $mid + 1, $high);
} else {
return binRecSearch($arr, $item, $low, $mid - 1);
}
}
return -1;
}
网友评论