常见搜索算法实现

顺序搜索

顺序搜索又名线性搜索是最基本的搜索算法,实现方式很简单,是按照序列原有顺序对数组进行遍历比较查询的基本查找算法。

算法实现

1
2
3
4
5
6
7
8
9
function search($arr, $item) {
foreach ($arr as $key => $value) {
if ($value == $item) {
return $key;
}
}

return -1;
}

二分搜索

二分搜索要求被搜索的数据结构已经排序,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。实现步骤如下:

  • 选择数组中的中间值;
  • 如果选中值是待搜索值,那么算法执行完毕;
  • 如果待搜索值比选中值要小,则返回步骤1并在选中值左边的子数组中寻找;
  • 如果待搜索值比选中值要大,则返回步骤1并在选中值右边的子数组中寻找;

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function binarysearch($arr, $value) {
$low = 0;
$high = count($arr)-1;
while ($low <= $high) {
$mid = floor(($low+$high)/2);
$item = $arr[$mid];
if ($item > $value) {
$high = $mid-1;
} elseif ($item < $value) {
$low = $mid+1;
} else {
return $mid;
}
}

return -1;
}
有用就打赏一下作者吧!