Warning在本文中，我将为退伍军人介绍不同的搜索算法及其复杂性。因为力求通俗易懂，文字可能会更长一些。可以先记下来，每天花时间阅读理解。支持本文的Github，欢迎各位老牌明星，会持续更新。开局类似于排序。搜索或搜索也是最常用的算法之一。无论我们是搜索数据库还是文件，我们实际上都是在使用某种搜索算法来定位我们要查找的数据。执行搜索最常见的方法是将每个项目与我们要查找的数据进行比较，这称为线性搜索或顺序搜索。这是执行搜索的最基本方法。如果列表中有n个项目。在最坏的情况下。我们必须搜索n个项目才能找到特定的项目。以下遍历数组以查找项目。functionlinearSearch(array$arr,int$needle){for($i=0,$count=count($arr);$i<$count;$i++){if($needle===$arr[$i]){返回真；}}returnfalse;}线性搜索复杂度最佳时间复杂度O(1)最差时间复杂度O(n)平均时间复杂度O(n)空间时间复杂度O(1)二分搜索线性搜索平均时间复杂度或者最差时间复杂度O(n),它不会随着要搜索的数组顺序的变化而变化。因此，如果数组中的项目按特定顺序排序，我们就不必进行线性搜索。我们可以通过执行选择性搜索来获得更好的结果。最流行和最知名的搜索算法是“二分搜索”。虽然有点像二叉搜索树，但是我们可以在不构造二叉搜索树的情况下使用这个算法。函数binarySearch(array$arr,int$needle){$low=0;$high=count($arr)-1;while($low<=$high){$middle=(int)(($high+$low)/2);如果（$arr[$middle]<$needle）{$low=$middle+1;}elseif($arr[$middle]>$needle){$high=$middle-1;}else{返回真；}}returnfalse;}在二分搜索算法中，我们从数据的中间开始，检查中间的项目是小于还是大于我们正在寻找的项目，然后决定走哪条路。这样，我们将列表分成两半并完全丢弃一半，如下图所示。递归版本：functionbinarySearchRecursion(array$arr,int$needle,int$low,int$high){if($high<$low)returnfalse;$middle=(int)(($high+$low)/2);如果（$arr[$middle]<$needle）{返回binarySearchRecursion（$arr，$needle，$middle+1，$high）；}elseif($arr[$middle]>$needle){returnbinarySearchRecursion($arr,$needle,$low,$middle-1);}else{返回真；}}二分搜索复杂度分析对于每次迭代，我们将数据分成两半，丢弃一半，使用另一半进行搜索。分别经过1、2、3次迭代后，我们的链表长度逐渐减小为n/2、n/4、n/8...。因此，我们可以发现，经过k次迭代后，只剩下n/2^k项.最后的结果是n/2^k=1，然后我们两边取对数得到k=log(n)，这是二分查找算法运行时复杂度最差的。最佳时间复杂度O(1)最差时间复杂度O(logn)平均时间复杂度O(logn)空间时间复杂度O(1)重复二分查找有这样一个场景，如果我们有一个有重复数据的数组，如果我们想从数组找到2第一次出现的位置，使用前面的算法会返回第5个元素。然而，从下图我们可以清楚地看到，正确的结果告诉我们它不是第5个元素，而是第2个元素。因此，需要修改上面的二分查找算法，修改为重复查找，直到元素第一次出现才停止查找。函数repetitiveBinarySearch(array$data,int$needle){$low=0;$高=计数（$数据）；$firstIndex=-1;while($low<=$high){$middle=($low+$high)>>1;如果（$data[$middle]===$needle）{$firstIndex=$middle;$high=$middle-1;}elseif($data[$middle]>$needle){$high=$middle-1;}else{$low=$middle+1;}}return$firstIndex;}首先我们检查mid对应的值是不是我们要找的值。如果是，那么我们就把中间的索引指定为第一次出现的索引，我们继续检查中间元素左边的元素，看我们要找的值是否再次出现。然后继续迭代直到low>low>high。如果未再次找到该值，则第一次出现的是项目第一个索引处的值。如果不是，则照常返回-1。让我们运行一个测试，看看代码是否正确：publicfunctiontestRepetitiveBinarySearch(){$arr=[1,1,1,2,3,4,5,5,5,5,5,6,7,8,9,10];$firstIndex=repetitiveBinarySearch($arr,6);$this->assertEquals(11,$firstIndex);}结果发现是正确的。至此我们可以得出结论，二分查找肯定比线性查找快。然而，这一切的前提是数组已经排序。对未排序的数组应用二进制搜索可能会导致不正确的结果。可能会出现一种情况，我们不确定一个数组是否已经排序。现在的问题是，我是不是应该先对数组进行排序，然后再应用二分查找算法呢？还是继续使用线性搜索算法？一个有n个项目的数组的小想法，它们没有排序。由于我们知道二分查找速度更快，所以我们决定先排序，然后再使用二分查找。但是，我们知道最好的排序算法的最坏时间复杂度是O(nlogn)，而对于二分查找，最坏情况复杂度是O(logn)。因此，如果我们在排序后应用二分查找，复杂度将为O(nlogn)。然而，我们也知道，对于任何线性或顺序搜索（排序或未排序），最坏的时间复杂度是O(n)，这显然优于上述方案。考虑另一种情况，我们需要多次搜索给定的数组。我们将k表示为我们要搜索数组的次数。如果k为1，那么我们可以很容易地应用前面的线性搜索方法。如果k的值小于数组的大小，暂时用n来表示数组的大小。如果k的值接近或大于n，那么我们在应用线性方法时就会遇到一些问题。假设k=n，线性搜索的复杂度为O(n2)。现在，如果我们排序然后搜索，即使k更大，排序也只需要O(nlogn)时间。那么，每次搜索的复杂度为O(logn)，n次搜索的复杂度为O(nlogn)。如果我们在这里运行最坏的情况，排序然后搜索k次的总复杂度是O(nlogn)，这显然比顺序搜索要好。我们可以得出结论，如果某些查找操作的次数小于数组的长度，最好不要对数组进行排序，只进行顺序查找。但是，如果搜索操作的数量与数组的大小相比很大，最好先对数组进行排序，然后再使用二分查找。二分查找算法有许多不同的版本。我们可以通过计算决定选择下一个使用哪个索引，而不是每次都选择一个中间索引。我们现在看一下二分搜索算法的两种变体：插值搜索和指数搜索。插值搜索在二分搜索算法中，搜索过程总是从数组的中间开始。如果一个数组是均匀分布的，而我们要查找的数据可能靠近数组的末尾，那么从中间搜索可能不是一个好的选择。在这种情况下，插值搜索可能非常有用。插值搜索是对二分搜索算法的改进。插值搜索可以根据搜索到的值选择到达不同的位置。例如，如果我们在数组开头附近搜索一个值，它将直接转到数组的第一部分而不是中间部分。使用公式计算位置，如下所示，我们将从通用的mid=(low*high)/2转移到更复杂的方程式。如果搜索值更接近arr[high]，此公式将返回更高的索引；如果该值更接近arr[low]，则返回更低的索引。函数interpolationSearch(array$arr,int$needle){$low=0;$high=count($arr)-1;while($arr[$low]!=$arr[$high]&&$needle>=$arr[$low]&&$needle<=$arr[$high]){$middle=intval($low+($针-$arr[$low])*($high-$low)/($arr[$high]-$arr[$low]));如果（$arr[$middle]<$needle）{$low=$middle+1;}elseif($arr[$middle]>$needle){$high=$middle-1;}else{return$middle;}}if($needle==$arr[$low]){return$low;}返回-1；}插值搜索需要更多的计算步骤，但是如果数据是均匀分布的，这个算法的平均复杂度是O(log(logn))，比二分搜索的复杂度O(logn)要好很多。另外，如果值的分布不均匀，我们也要小心。在这种情况下，可能需要重新评估插值搜索的性能。下面我们探讨另一种二分搜索的变体，称为指数搜索。指数搜索在二分搜索中，我们在整个列表中搜索给定数据。指数搜索通过确定搜索的下限和上限来改进二分搜索，这样我们就不会搜索整个列表。它减少了我们在搜索过程中比较的元素数量。索引搜索通过以下两个步骤完成：我们通过找到第一个索引k来确定边界大小，其中2^k的值大于搜索项。现在，2^k和2^(k-1)分别成为上限和下限。使用上述边界执行二分查找。我们看PHP函数exponentialSearch(array$arr,int$needle)实现的代码：int{$length=count($arr);如果（$length==0）返回-1；$绑定=1；while($bound<$length&&$arr[$bound]<$needle){$bound*=2;}返回binarySearchRecursion($arr,$needle,$bound>>1,min($bound,$length));}我们把$needle出现的位置记录为i，那么我们第一步的时间复杂度就是O(logi)。表示我们的while循环需要执行O(logi)次才能找到上限。由于下一步应用二分查找，所以时间复杂度也是O(logi)。我们假设j是我们最后一个while循环的执行次数，那么我们这次二分查找需要搜索的范围是2^j-1到2^j，j=logi，也就是我们的时间复杂度二分查找需要对这个范围求log2，即整个索引查找的时间复杂度为2O(logi)，省略常数为O(logi)。最佳时间复杂度O(1)最差时间复杂度O(logi)平均时间复杂度O(logi)空间时间复杂度O(1)哈希查找哈希表在搜索操作方面可以是非常高效的数据结构。在哈希表中，每条数据都有一个与之关联的唯一索引。如果我们知道要看哪个索引，我们可以很容易地找到对应的值。通常，在其他编程语言中，我们必须使用单独的哈希函数来计算存储值的哈希索引。哈希函数旨在为相同的值生成相同的索引并避免冲突。在PHP的底层C实现中，数组本身就是一个哈希表。由于数组是动态的，所以不用担心数组溢出。我们可以将值存储在关联数组中，这样我们就可以将值与键关联起来。functionhashSearch(array$arr,int$needle){returnisset($arr[$needle])？true:false;}树搜索搜索分层数据的最佳选择之一是创建搜索树。在“理解和实现树”一章中，我们看到了如何构建二叉搜索树并提高搜索效率，并介绍了遍历树的不同方法。现在，继续讨论两种最常用的树搜索方法，通常称为广度优先搜索(BFS)和深度优先搜索(DFS)。BreadthFirstSearch(BFS)在树结构中，根节点与其子节点相连，每个子节点也可以继续表示为一棵树。在广度优先搜索中，我们从一个节点（主要是根节点）开始，先访问所有邻居节点，然后再访问其他邻居节点。换句话说，我们在使用BFS时必须逐层移动。使用BFS，将获得以下序列。伪代码如下：procedureBFS(Noderoot)Q:=emptyqueueQ.enqueue(root)while(Q!=empty)u:=Q.dequeue()foreachnodewthatischildnodeofuQ.enqueue(w)endforeachendwhileendprocedure下面是PHP代码。类TreeNode{public$data=null;公共$children=[];公共函数__construct(string$data=null){$this->data=$data;}publicfunctionaddChildren(TreeNode$treeNode){$this->children[]=$treeNode;}}类树{public$root=null;公共函数__construct(TreeNode$treeNode){$this->root=$treeNode;}publicfunctionBFS(TreeNode$node):SplQueue{$queue=newSplQueue();$visited=newSplQueue();$queue->enqueue($node);while(!$queue->isEmpty()){$current=$queue->dequeue();$visited->enqueue($current);foreach($current->childrenas$children){$queue->enqueue($children);}}返回$visited;}}如果要查找节点是否存在，可以设置当前节点值，加个简单的条件判断即可。BFS最坏的时间复杂度是O(|V|+|E|)，其中V是顶点或节点的数量，E是边或节点之间的连接的数量，最坏情况的空间复杂度是O(|V|).图的BFS与上面的类似，但略有不同。由于图是循环的（可以创建循环），我们需要确保不会重复访问同一节点以创建无限循环。为了避免重新访问图节点，有必要跟踪已经访问过的节点。可以使用队列，也可以使用图着色算法来解决。深度优先搜索（DFS）深度优先搜索（DFS）是指从一个节点开始搜索，从目标节点开始通过分支到达尽可能深的节点。DFS与BFS不同。简单来说，DFS是深入挖掘而不是先扩散。然后DFS在到达一个分支的末尾时向上回溯，移动到下一个可用的相邻节点，直到搜索结束。还是上面这棵树，这次我们会得到一个不同的遍历顺序：从根开始，然后访问第一个孩子，也就是3。然后，到3的孩子，如此反复，直到到达树枝的底部.在DFS中，我们将递归地进行。每个节点v的过程DFS(Nodecurrent)是当前DFS(v)的子节点endforeachend过程publicfunctionDFS(TreeNode$node):SplQueue{$this->visited->enqueue($node);如果($node->children){foreach($node->childrenas$child){$this->DFS($child);}}return$this->visited;}如果你需要使用迭代实现，你必须记住使用堆栈而不是Notaqueue来跟踪下一个要访问的节点。下面使用迭代法publicfunctionDFS(TreeNode$node)的实现：SplQueue{$stack=newSplStack();$visited=newSplQueue();$堆栈->推送（$节点）；while(!$stack->isEmpty()){$current=$stack->pop();$visited->enqueue($current);foreach($current->childrenas$child){$stack->push($child);}}return$visited;}这看起来与BFS算法非常相似。主要区别在于使用堆栈而不是队列来存储访问过的节点。它会对结果产生影响。上面的代码会输出810141336741。这和我们算法使用迭代的输出结果不一样，但是结果没有错。因为栈是用来存放特定节点的子节点的。对于值为8的根节点，先将第一个值为3的子节点入栈，再将10入栈。由于10稍后被压入堆栈，因此它遵循LIFO。因此，如果我们使用堆栈实现DFS，输出总是从最后一个分支开始到第一个分支。可以在DFS代码中做一些小的调整来达到预期的效果。公共函数DFS(TreeNode$node):SplQueue{$stack=newSplStack();$visited=newSplQueue();$堆栈->推送（$节点）；while(!$stack->isEmpty()){$current=$stack->pop();$visited->enqueue($current);$current->children=array_reverse($current->children);foreach($current->childrenas$child){$stack->push($child);}}return$visited;}由于栈遵循后进先出（LIFO），通过倒置，可以保证先访问第一个节点，因为顺序颠倒了，栈实际上是作为队列工作的.如果我们要搜索一棵二叉树，就不需要任何倒置，因为我们可以选择先压入右孩子，然后先弹出左孩子。DFS的时间复杂度与BFS类似。大家注意点，别迷路了，以上就是本文的全部内容，能看到这里的都是人才。前面说了PHP的技术点很多，也是因为太多了，写的太多了，写完了也不会看太多，所以我这里整理成了PDF和文档，有需要的可以点击进入密码：想了解更多内容可以访问【比大厂】优质PHP架构师教程目录，只要会看，就可以保证你的薪水会上升到一个更高的水平（不断更新）。以上内容希望对大家有所帮助，很多PHPer在进阶的时候总会遇到一些问题和瓶颈。业务代码写多了，没有方向感，就不知道从哪里入手改进。我整理了一些这方面的资料，包括但不限于：高扩展、高性能、高并发、服务器性能调优、TP6、laravel、YII2、Redis、Swoole、Swoft、Kafka、Mysql优化、shell脚本、Docker、微服务,Nginx等知识点进阶进阶干货需要的可以免费分享给大家，需要的可以加我的PHP技术交流群953224940
