PHP数组顺序查找法和二分查找法介绍

本文介绍PHP数组顺序查找法和二分查找法的基本使用方法和原理。

一、顺序查找法

基本原理

顺序查找法是比较基本的查找方法，根据照数组中元素的保存顺序，利用待查找的值与数组中的元素从前往后一个一个地进行比较，直到找到目标值(查找成功)或查找失败。

优点

该查找方法对数组中元素的排序没有要求，可以看出顺序查找法它的适应性比较强。

缺点

每次查找元素时都需要重新遍历一次数组，这使得它效率比较低。

实现代码    

主要是通过foreach循环的方式来实现顺序查找法

/**
 * 顺序查找法
 * @param array $arr 数组
 * @param int $find 待查找的值
 */
function search($arr, $find) {
	foreach ($arr as $k => $v) {
		if ($find == $v) {
			return "{$find}在数组中的键名为：$k";//查找成功
		}
	}
	return false;//查找失败
}

$arr = [1,3,5,8];
search($arr,8);//返回：8在数组中的键名为：3
search($arr,9);//返回：false

二、二分查找法

基本原理

二分查找法是针对有序数组的一种查找法。其查询效率非常高，性能较好。具体实现原理是，每次将查找值与数组中间位置元素的值进行比较，相等返回。不等则排除掉数组中一半的元素，然后根据比较结果大或小，再与数组中剩余一半中间位置元素的值进行比较，以此类推，直到找到目标值或查找失败。  

优点

查询效率高，性能好。

缺点

只适用有序数组。

实现代码

通过递归函数的方式来实现二分查找法

/**
 * 二分查找法
 * @param array $arr 数组
 * @param integer $start 开始位置
 * @param mixed $end 结束位置
 * @param int $find 待查找的值
 */
function search($arr, $start, $end, $find) {
	$mid = intval(($start+$end) / 2);// 找出数组中间元素键值

	/**
	 * 基本的判断可以分为三种：中间值大于待查找值、中间值小于待查找值、中间值刚好等于待查找值
	 */
	if ($start > $end) {
		// 传入的起始位置大于数组最大的元素键值，视为查找失败
		return '查找失败';
	} elseif ($arr[$mid] > $find) {
		// 中间值大于待查找值,去掉右边的数组元素，保留左边
		return search($arr, $start, $mid-1, $find);
	} elseif ($arr[$mid] < $find) {
		// 中间值小于待查找值,去掉左边的数组元素，保留右边
		return search($arr, $mid+1, $end, $find);
	} else {
		//中间值刚好等于待查找值
		return $mid;
	}
}


$arr = [0,1,3,5,8];
$len = count($arr);
echo search($arr,0,$len-1,3);//3在数组中的键名为：2
echo search($arr,0,$len-1,8);//8在数组中的键名为：4
echo search($arr,0,$len-1,9);//返回：'查找失败'
echo search($arr,2,$len-1,1);//返回：'查找失败'

以上是对顺序查找法和二分查找法的介绍。