algorithm - 二进制搜索与线性搜索(数据结构和算法)

Question

试图围绕一些基本和常见的算法进行思考。我目前对这个问题的理解是粗体。

( 1 ) 假设我们有一个包含 n 个项目的排序数组:二分查找最多比较元素多少次？

我一直看到“0(log(n))”作为此类问题的一般答案弹出，但我不明白为什么。没有一个整数可以回答这个问题(即 2 或 3？)

( 2 ) 假设我们有一个包含 n 项的数组:线性搜索最多比较元素多少次？

同样，与上面相同，但现在“0(n)”似乎是这个问题的一般答案。同样，我真的不明白这个答案背后的力量，并质疑为什么没有一些整数答案？

( 3 ) 有人可以解释一个线性搜索比二分搜索更好的例子吗？

从我收集到的信息来看，如果可能的话，二分查找通常似乎是更好的选择，因为它的速度很快。我无法确定线性搜索何时是更好的选择。

Answer 1

关于 1 和 2，如果提供绝对数字作为输入的大小，则绝对数字作为答案是可能的。由于问题询问的是任意大小的数组(长度为 n)，因此答案也以这些术语给出。
你可以阅读更多关于 big O notation 的信息有关详细信息，但基本上 O(n) & O(log n) 表示 order of n & order of log(n) 分别。例如，如果输入大小为 100，则使用线性搜索进行比较的元素数量也将在 100 的数量级，而使用二分搜索则需要比较 ~ log(100) 个元素。
至于3，二分查找需要对输入进行排序...