乐趣区

关于php:PHP数据结构线性查找与二分查找

jiezi

欢送来到查找的世界，在学习完各种数据结构之后，总算走到了这一步，不晓得大家有什么感想呢？反正我是边学边忘，当初让我去说说图的那几个算法还是在蒙圈的状态中。不过学习嘛，就是一步一步的来，临时搞不懂的货色其实也是能够放一放的。突破砂锅和坚定不移当然是好的道德，但有些货色可能真的是须要工夫去消化的，甚至可能是须要实在的我的项目经验能力彻底搞明确。在咱们编程行业来说就是典型的这种实际的学习模式成果会更好，很多人在上大学的时候对于数据结构以及其它专业课都是以死记硬背为主，包含上了多少年班的同学可能都没有在业务代码中真正的应用过什么算法，所以了解它们的确是十分艰难的。这时，咱们能够临时劳动一下，转换一下思路，学习最次要的就是预习和温习，在这次学习完之后，未来再进行屡次的温习，钻研各种不同的材料，迟早有一天大家都能搞明确的。

明天的内容其实就非常简单了，能够说是除了线性表之外最简略的内容。咱们只钻研两个十分高级的查找，那就是程序查找和折半查找。置信不少同学可能早就会了，个别培训机构讲数据结构和算法时，查找必讲二分，排序必讲冒泡，更不用说正规大学对口业余出身的同学了。当然，这两个也是非常简单的，不论你有没有根底，咱们一起来看看吧。

不论你是什么算法题，还是在理论的业务开发中，查找都是十分重要的，甚至可能比排序还要重要。想想你终日面向数据库编程是在干嘛？不就是 CRUD 嘛，其中大部的业务还都是以搜寻查找居多，咱们在优化数据库时，也次要是优化各种查问语句。当然，要说到数据库的查找那就太浅近了，当前咱们学习 MySQL 相干的常识时再具体解说，特地是索引中的 B+ 树，就是数据结构和算法的核心思想的体现。好吧，不吹牛了，也不敢在这里多说了，因为本人也没钻研透呢。

线性查找（程序查找）

顾名思义，不论是叫线性还是叫程序，很显著，就是一条数据一条数据的比照上来就好啦。

function SearchSeq($sk, $arr)
{for ($i = 0; $i < count($arr); $i++) {if ($sk == $arr[$i]) {
            echo $i, PHP_EOL;
            break;
        }
    }
    echo "线性查找次数：" . $i, PHP_EOL;
}

嗯，真的是连解释都不想解释了，这段代码要是看不懂的话就先去温习下根本的循环和条件判断语句吧！很显著，一次线性查找的工夫复杂度就是 O(N)。

二分查找（折半查找）

既然都这么简略，那么咱们再间接给出折半查找的代码。

function SearchBin($sk, $arr){
    $left = 0;
    $right = count($arr) - 1;
    $i = 0;
    while ($left <= $right) {
        $i++;
        $mid = (int) (($left + $right) / 2);
        if ($arr[$mid] > $sk) {$right = $mid - 1;} else if ($arr[$mid] < $sk) {$left = $mid + 1;} else {
            echo $mid, PHP_EOL;
            break;
        }
    }
    echo "折半查找次数：" . $i, PHP_EOL;
}

折半查找的前提是数据必须是有序的，这样咱们就能够依据数据问题的长度来获取两头的数，而后跟要比照的数进行比拟，如果小于这个数，就在前一半数据中查找，如果大于这个数，就在后一半局部中进行查找。一会看例子再具体阐明。

比照

两个算法其实都很简略，咱们间接看看他们的运行状况和效率区别。

$arr = [5, 6, 19, 25, 4, 33, 56, 77, 82, 81, 64, 37, 91, 23];

// 输出 56
fscanf(STDIN, "%d", $searchKey);

SearchSeq($searchKey, $arr);
// 6
// 线性查找次数：6

sort($arr);
print_r($arr);

SearchBin($searchKey, $arr);
// 8
// 折半查找次数：3

首先咱们定义了一个数组，其实就是轻易给了一些数据。而后输出一个数据，查找它在数组中的地位。比方咱们在测试代码中输出了 56，线性查找是循环进行了 6 次，找到 56 所在的地位为下标 6 的地位。

对于折半查找来说，咱们须要先给数组排序，这时 56 会排在下标为 8 的地位，而在折半查找的循环中，咱们只循环了 3 次就找到了这个地位。是不是感觉快了很多，一下就快了一倍。这可不是它的真正实力哦，折半查找的实在实力是 对数 级别的效率，也就是它的工夫复杂度为 O(logN)。咱们先来联合下面的代码看下它这三次循环都干了什么。

  • 第一次进入，mid 为 6 (0+13=13，除 2)，下标为 arr[6] 的值为 3，比 56 小，所以 left = 6+1 = 7
  • 第二轮循环，mid 为 10（7+13=20，除 2），下标为 arr[10] 的值为 77，比 56 大，所以 right = 10-1 = 9
  • 第三轮循环，mid 为 9（7+9=16，除 2），下标为 arr[8] 的值为 56，完结

其实很多猜数字的游戏也都是这么玩的，比方给你一个范畴，0-100 的数，猜他写下的是哪个数，最快最简略的办法也就是这种折半查找的形式，咱们只须要最多 7 次就能够猜出 100 以内的数。很显著，这就是对数的威力。上面咱们再来看一个更直观的，十万个有序的数，咱们就找最初那一个数，看看程序查找和折半查找能有多大差距。

$arr = range(1, 100000);
$searchKey = 100000;

SearchSeq($searchKey, $arr);
// 99999
// 线性查找次数：99999

SearchBin($searchKey, $arr);
// 99999
// 折半查找次数：17

嗨不嗨，这就是对数的威力！！咱们须要 2 的 7 次刚才能笼罩 100 以内的数，但咱们只须要 2 的 17 次方，就能笼罩十万以内的数，这个效率差距还是随着 N 的越来越大而越来越显著的。

总结

明天的内容是不是很简略，虽说内容简略，然而咱们却见识到了不同算法效率之间的微小差别。当然，折半查找也有其自身的局限，那就是数据必须是的序的，当然，在适合的状况下咱们也能够选用一个 O(logN) 的排序算法，这样总体的工夫复杂度就还能放弃在对数级别了。总之，先把握好这些简略的内容，千万别在面试的时候连这一关都过不了哦！

测试代码：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/6. 查找 /source/6.1 线性查找与二分查找.php

参考文档：

《数据结构》第二版，严蔚敏

《数据结构》第二版，陈越

《数据结构高分笔记》2020 版，天勤考研

各自媒体平台均可搜寻【硬核项目经理】

退出移动版