数据结构中搜索方法的比较

在不同的情况下，我们使用不同的搜索方案来查找某些键。在这一部分，我们将看到两种搜索技术的基本差别，即顺序搜索和二分搜索。

顺序搜索	二分搜索
时间复杂度为 O(n)	时间复杂度为 O(log n)
找出在常量时间内出现在首个位置的键	找出在常量时间内出现在中间位置的键
容器中的元素的顺序不会产生影响。	容器中的元素必须按顺序排列
可以使用数组和链表来实现	它不能直接实现为链表。我们需要更改列表的基本规则来实现
算法本质上是迭代的	算法技术是分而治之。
算法很容易实现，并且需要的代码量较少。	算法有点复杂。它需要的代码量较多。
对最坏的情况来说，需要进行 N 次比较。	在最坏情况下，进行 Log n 次比较就足够了。

Arnab Chakraborty

更新于： 2019 年 8 月 27 日

5K+ 次浏览

完成课程即可获得认证