PHP之二分法查找

发布于：2020-12-07 08:28:42

二分法查找，需要一个是递增的数组。

原理：找出数组的中间位置，从中间位置把数组一分为二，先拿中间的值和要查找的值进行对比。
如果一致，直接返回中间位置；
如果 中间的值 比 要查找的值 大，说明要查找的值在左边，再去左边进行查找，重复上面步骤，直到匹配到或查完数组；
如果 中间的值 比 要查找的值 小，说明在右边，去右边查找。

function search($array, $value, $low = 0, $high = 0){
	// 初始化赋初值
	if($high == 0 && count($array) > 0){
		$high = count($array);
	}
	if($low <= $high){		// 左边坐标 不能大于 右边坐标
		// 找到中间坐标
		$mid = floor(($low + $high) / 2);
		
		if($array[$mid] == $value){		// 中间坐标的值刚好等于要查找的值，直接返回坐标
			return $mid;
		}else if($array[$mid] > $value){		// 中间坐标的值 比 要查找的值 大，进入左边继续查找
			return search($array, $value, $low, $mid-1);
		}else{		// 反之，中间坐标的值 比 要查找的值 小，进入右边继续查找
			return search($array, $value, $mid+1, $high);
		}
	}
	echo '没有找到该值';
}

$array = array(2, 3, 6, 8, 13, 16, 23, 27, 39, 40);
echo search($array, 6);