常见搜索算法实现

顺序搜索

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

算法实现

function search($arr, $item) {
	foreach ($arr as $key => $value) {
		if ($value == $item) {
			return $key;
		}
	}

	return -1;
}

二分搜索

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

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

算法实现

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;
}