常用查找算法

• 1、顺序查找：
  • 顺序查找实例：
• 2、二分查找：

1、顺序查找：

对某个数组，按照顺序，一个一个比较，找到你要的数据。

顺序查找实例：

<?php  
//顺序查找数组中某个数
//如从一个数组中找到一个数：34
//$arr = array(23,45,67,34,9,34,6)如果查到则输出下标，否则输出查无此数

$arr = array(23,45,67,34,9,34,6);
//设一个标志位
$flag = false;
foreach($arr as $x => $x_val)
{

    if ($x_val == 34)
    {
        echo 'arr['.$x.']=34'."<br>";
        $flag = true;
    }
}
if ($flag==false)
{
    echo "查无此数！";
}   
?>

2、二分查找：

首先找到数组中间这个数，然后与要查找的数比较，如果要查找的数大于中间这个数，则说明应该向后找，否则向前找，如果想等，则说明找到。

前提：该数组必须是有序数列，如果该数组无序，必须先排序后查找

递归形式：

<?php  
//二分查找数组中某个数
//如从一个数组中找到一个数：134
//$arr = array(23,45,67,89,90,134,236)如果查到则输出下标，否则输出查无此数

function binarySearch(&$arr,$val,$leftindex,$rightindex)
{
    if($rightindex < $leftindex)
    {
        echo "查无此数！";
        return 0;
    }
    //四舍五入取整数值
    $middleindex = round(($leftindex + $rightindex)/2);
    if($val > $arr[$middleindex])
    {
        binarySearch($arr,$val,$middleindex + 1,$rightindex);
    }
    elseif($val < $arr[$middleindex])
    {
        binarySearch($arr,$val,$leftindex,$middleindex - 1);
    }
    else
    {
        echo 'arr['."$middleindex".']=134'."<br>";
    }
}
    $arr = array(23,45,67,89,90,134,236);
//  $leftindex = 0;左下标
//  $rightindex = count($arr)-1;右下标
//  $val = 134;要找的值
    binarySearch($arr,134,0,count($arr) - 1)
?>

非递归形式：

$nums = [-1, 0, 3, 5, 9, 12, 13];
$target = 9;
function search($nums, $target)
{
    if (empty($nums)) {
        return -1;
    }
    $l = 0;
    $r = count($nums) - 1;
    while ($l <= $r) {
        $mid = ceil(($l + $r) / 2);
        if ($nums[$mid] == $target) {
            return $mid;
        } elseif ($nums[$mid] > $target) {
            $r = $mid - 1;
        } else {
            $l = $mid + 1;
        }
    }
    return -1;
}

var_dump(search($nums, $target));