二分查找

发布于 / 1年前 - 更新于 / 1年前


前言

在一个有序的数组中查找给定目标值是否存在,存在则返回其下标

思路

  1. 首先找到左(left)右(right)下标边界值(即0和leng-1)
  2. 已经明确目标值的下标一定在left和right之间
  3. 然后循环找到left和right的中间下标 mid=(mid = (left + (rightright-left)) / 2
  4. 对比下标为$mid的值和目标值对比
  5. 下标$mid的值等于目标值,则找到了,返回当前下标 $min
  6. 下标mid的值小于目标值,则代表目标值的下标大于mid,重新定义左边界值left=left=mid+1,执行下一次循环
  7. 下标mid的值大于目标值,则代表目标值的下表小于mid,重新定义右边界值right=right=mid-1,执行下一次循环
  8. 主要细节为重新定义left和right的值然后再找left和right的中间值
function search($nums, $target) { if(empty($nums) ){ return -1; } $left = 0; $right = count($nums) - 1; // 以上确定左右边界 while($left <= $right){ // 左右边界的中间值 $mid = intval( $left + ($right-$left)/2 ); if($nums[$mid] == $target){ return $mid;// 找到返回 }elseif($nums[$mid] < $target){ //目标值在二分的右,左边界值设置为中间值+1,继续下次循环查找 $left = $mid+1; }else{ //目标值在二分左。右边界值设置为中间值-1,继续下次循环查找 $right = $mid-1; } } return -1; } $target = 98; $nums = [1,3,4,6,7,9,23,45,56,67,78,89,98,123,234,456,567,789,999]; $index = search($nums,$target);

本作品采用《CC 协议》,转载必须注明作者和本文链接