PHP查找算法之二分查找(折半查找)

折半查找意为从把数组从中间分成两半，找到一个中间值，然后进行判断，首先这个数组一定是从大到小或者从小到大排好序的。

下面的代码里数组是从小到大排序的。

递归形式的：

<?php
//定义一个从小到大排好序的数组
$arr = [12 , 34 , 43 , 56 , 77 , 86 , 88 , 90 , 99 , 101];
//要查找的数字
$num = 88;
$count = count($arr);
//二分查找(折半查找)递归
function search($arr , $num , $start , $stop){
	//计算数组中间位置并取出对应的值
	$mkey = ceil(($start + $stop)/2);
	//判断取出来的中间值是否是要查找的值,如果是直接返回对应索引
	if ($arr[$mkey] == $num) {
		return $mkey;
	}
	//判断中间位置的值是否大于要查找的值,那么就从左边区域查找,起始位置不变,结束位置=中间位置-1
	if ($arr[$mkey] > $num) {
		$stop = $mkey - 1;
	}
	//判断中间位置的值是否小于要查找的值,那么就从右边区域查找,结束位置不变,起始位置=中间位置+1
	if ($arr[$mkey] < $num) {
		$start = $mkey + 1;
	}
	//如果起始位置大于结束位置那么就终止
	if ($start > $stop) {
		return false;
	}

	return search($arr , $num , $start , $stop);
}
print_r(search2($arr , $num , 0 , $count));

非递归形式的：

<?php
//定义一个从小到大排好序的数组
$arr = [12 , 34 , 43 , 56 , 77 , 86 , 88 , 90 , 99 , 101];
//要查找的数字
$num = 88;
$count = count($arr);
//二分查找(折半查找)非递归
function search2($arr , $num , $start , $stop){
	//如果其实位置小于等于结束位置的话就走循环,否则终止
	while ($start <= $stop) {
		//计算数组中间位置并取出对应的值
		$mkey = ceil(($start + $stop)/2);
		//判断中间位置的值是否是要查找的值,如果是直接返回对应的下标
		if ($arr[$mkey] == $num) {
			return $mkey;
		}
		//判断中间位置的值是否大于要查找的值,那么就从左边区域查找,起始位置不变,结束位置=中间位置-1
		if ($arr[$mkey] > $num) {
			$stop = $mkey - 1;
		}
		//判断中间位置的值是否小于要查找的值,那么就从右边区域查找,结束位置不变,起始位置=中间位置+1
		if ($arr[$mkey] < $num) {
			$start = $mkey + 1;
		}
	}

	//结束
	return false;
}

print_r(search2($arr , $num , 0 , $count));