文章目录 [+]
二分法简单原理
想要写出二分法查找的代码，首先要懂得二分法实现查找的原理。注：前提为有序的数组：
要知道中间位置就需要知道起始位置和结束位置，然后取出中间位置的值来和我们的值做对比。
如果中间值大于我们的给定值，说明我们的值在中间位置之前，此时需要再次二分，因为在中间之前，所以我们需要变的值是结束位置的值，此时结束位置的值应该是我们此时的中间位置。
反之，如果中间值小于我们给定的值，那么说明给定值在中间位置之后，此时需要再次将后一部分的值进行二分，因为在中间值之后，所以我们需要改变的值是开始位置的值，此时开始位置的值应该是我们此时的中间位置，直到我们找到指定值。
或者中间值等于最初的起始位置，或结束位置（此时说明给定值未找到）
php呈现方式1(递归)
function searchValue($array, $searchValue, $low = 0, $high = 0)
{
//如果数组不为空，且最大值为初始值0
if (count($array) && $high == 0) {
$high = count($array) - 1 ;
}
//如果最小值<=最大值
if ($low <= $high) {
$mid = (int) (($low + $high) / 2);
//查找的值等于中间值，那么直接返回该值在数组的位置
if ($array[$mid] == $searchValue) {
return $mid;
}
if ($searchValue > $array[$mid]) {
//查找的值大于中间值，那么往后查找，最小值为当前值+1，最大值不变
return searchValue($array, $searchValue, $mid + 1, $high);
}else{
//查找的值小于当前中间值，那么往前找，最小值不变，最大值为最小值-1
return searchValue($array, $searchValue, $low, $mid - 1);
}
}
//未找到，返回-1
return -1;
}
$arr = [1,2,3,4,5,6,7,8,9,10];
echo searchValue($arr, 10);php呈现方式2（while）
$arr = [1,2,3,4,5,6,7,8,9,10];
$searchValue = 0;
$min = 0;
$max = count($arr) - 1;
$mid = (int) (($min + $max) / 2);
while (true) {
//如果最小值<=最大值
if ($min <= $max) {
//查找的值等于中间值，那么直接返回该值在数组的位置
if ($arr[$mid] == $searchValue) {
echo '位置：' . $mid;die;
}
if ($searchValue > $arr[$mid]) {
//查找的值大于中间值，那么往后查找，最小值为当前值+1，最大值不变
$min = $mid + 1;
}else{
//查找的值小于当前中间值，那么往前找，最小值不变，最大值为最小值-1
$max = $mid - 1;
}
//重置中间值
$mid = (int) (($min + $max) / 2);
}else{
echo '未找到';die;
}
}
发表评论