欢迎来到搜索的世界。在学习了各种数据结构之后，终于走到了这一步。你怎么认为？反正我是边学边忘，现在说说图的算法都还处于圈圈的状态。但是学习是循序渐进的，暂时不懂的东西其实可以放一边。打破砂锅，坚持不懈固然是好的品质，但有些东西可能真的需要时间去消化，甚至可能需要真正的项目经历才能完全理解。在我们的编程行业中，典型的是这种实用的学习形式会更好。很多人在大学的时候主要是死记硬背数据结构等专业课，包括已经上过很多年课的学生。业务代码中可能并没有真正用到什么算法，所以真的很难理解。这个时候，我们可以稍作休息，换个思路。最重要的是学习预习和复习。经过这次学习，我们以后会多次复习，研究各种资料。迟早，每个人都会明白我的意思。今天的内容其实很简单，可以说是线性表之外最简单的内容了。我们只研究两种非常初级的查找，顺序查找和二进制查找。相信很多同学可能早就知道了。一般的培训机构讲数据结构和算法的时候，肯定讲的是搜索的二分法，排序的冒泡，更何况是正规大学相应专业的学生。当然这两个也很简单，不管你有没有基础，一起来看看吧。不管你遇到什么算法问题，或者在实际业务开发中，查找都是非常重要的，甚至可能比排序更重要。想想你整天都在为数据库编程做什么？不就是CRUD吗？大多数业务都是搜索和搜索。我们在优化数据库的时候，主要是优化各种查询语句。当然，说到数据库搜索，就太高级了，我们在学习MySQL相关知识的时候会详细讲解，尤其是索引中的B+树，是数据核心思想的体现结构和算法。好了，我就不吹了，这里也不敢多说，因为我也没研究透。线性搜索（sequentialsearch）顾名思义，不管叫线性还是sequential，很明显就是将一份数据和一份数据进行比较。函数SearchSeq($sk,$arr){for($i=0;$i$sk）{$right=$mid-1;}elseif($arr[$mid]<$sk){$left=$mid+1;}else{echo$mid,PHP_EOL;休息;}}echo"Halvedsearchtimes:".$i,PHP_EOL;}半查找的前提是数据必须是有序的，所以我们可以根据数据问题的长度来获取中间的数，然后与要比较的数进行比较。如果小于这个数，则在前半部分数据中查找。如果大于这个数，则在下半场查找。我会看例子，稍后再详细解释。比较两种算法其实很简单，我们直接看它们的运行和效率差异。$arr=[5,6,19,25,4,33,56,77,82,81,64,37,91,23];//Input56fscanf(STDIN,"%d",$searchKey);SeqSeq($searchKey,$arr);//6//线性搜索次数：6sort($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以内的数字。显然，这就是对数的威力。接下来我们看一个更直观的，10万个有序数。让我们找到最后一个数字，看看顺序搜索和半搜索之间的差距有多大。$arr=range(1,100000);$searchKey=100000;SeqSeq($searchKey,$arr);//99999//线性搜索次数：99999SearchBin($searchKey,$arr);//99999//一半搜索次数:17嘿嘿，这就是对数的力量！！我们需要2的7次方来覆盖100以内的数字，但是我们只需要2的17次方来覆盖100,000以内的数字。这种效率差距随着N的增加而变得越来越明显。总结今天的内容是不是很简单？内容虽然简单，但是我们看到了不同算法在效率上的巨大差异。当然，半查找也有自身的局限性，就是数据必须是有序的。当然我们也可以在合适的情况下选择一种O(logN)的排序算法，这样整体的时间复杂度可以保持在对数级别。总之，先把这些简单的内容掌握好，面试的时候不要过不了这一关！测试代码：https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/6。搜索/source/6.1线性搜索和二分搜索.php参考文档：《数据结构》第二版，闫伟民《数据结构》第二版，陈越《数据结构高分笔记》2020版，天琴考研各自媒体平台可搜索【硬核项目经理】】
