二进制搜索与线性搜索（数据结构和算法）
Binary Search vs. Linear Search (data structures & algorithms)
试图围绕一些基本和常见的算法进行思考。我目前对这个问题的理解是 粗体。
( 1 ) 假设我们有一个包含 n 项的排序数组：二分查找最多比较元素多少次？
我一直看到“0(log(n))”作为此类问题的一般答案弹出，但我不明白为什么。没有一个整数可以回答这个问题（即 2 或 3？）
( 2 ) 假设我们有一个包含 n 项的数组：线性搜索最多比较元素多少次？
同样，同上，但现在'0(n)'似乎是这个问题的一般答案。再一次，我真的不明白这个答案背后的力量，并质疑为什么没有一些整数答案？
( 3 ) 有人可以解释一个线性搜索比二分搜索更好的例子吗？
从我收集到的信息来看，如果可能的话，二进制搜索通常似乎是更好的选择，因为它的速度很快。我无法确定线性搜索何时是更好的选择。
关于 1 和 2，如果提供绝对数字作为输入的大小，则绝对数字作为答案是可能的。由于问题询问的是任意大小的数组（长度 n），因此答案也以这些术语给出。
您可以阅读更多关于 big O notation 的详细信息，但基本上 O(n) 和 O(log n) 分别表示 order of n 和 order of log(n)。例如，如果输入大小为 100，则使用线性搜索的比较元素的数量也将在 100 的数量级，而使用二分搜索则需要比较 ~ log(100) 个元素。
至于3，二分查找需要对输入进行排序...
O 表示法是关于限制行为的。因此，二分查找将列表一分为二。要么您已经找到该项目，要么您有一半要搜索。因此 O(nlogn) 的限制行为 - 即在搜索树的叶子处。
线性搜索从头开始。最坏的情况（极限）是元素在最后）。
对于 (3)，如果该项目是列表中的第一个，那么您就中奖了。所以在那种情况下会更好
下面video提供了全面的解释。我希望它能帮助您理解二进制搜索和线性搜索之间的区别。
对于问题 3：
- 二进制搜索需要，排序序列。
- 对于序列 1,2,3,...,100。当要查找元素 1 时，线性搜索会更快。它只会检查第一个元素。
首先，您正在处理 O 表示法，因此 "whole number" 是不可能的。答案始终采用 O(f(n)) 格式，其中 f(n) 是 n 的某个函数。如果您不确定大 O 表示法是什么，那么从 http://en.wikipedia.org/wiki/Big_O_notation 开始可能会有帮助。
(1) 对排序数组进行二分查找，查找space 重复减半，直到找到元素。如果我们考虑一个理想的二进制搜索实现，其中每个操作都需要常数时间，在最坏的情况下，我们将需要检查大约 logn 个项目——这将花费 O(logn) 时间。至于 logn 背后的数学：它们并不难，但很难在 iPhone 上打出来。提示：Google 是你的朋友。
(2) 在未排序数组的线性搜索中，我们可能必须检查数组中的每一项。同样，这是一种简化，但假设我们算法中的每个操作都需要常数时间，我们必须至少查看 n 次。因此 O(n).
(3) (1) 和(2) 中必须搜索的数据有何不同？请记住，最佳排序是 O(nlogn).
试图围绕一些基本和常见的算法进行思考。我目前对这个问题的理解是 粗体。
( 1 ) 假设我们有一个包含 n 项的排序数组：二分查找最多比较元素多少次？
我一直看到“0(log(n))”作为此类问题的一般答案弹出，但我不明白为什么。没有一个整数可以回答这个问题（即 2 或 3？）
( 2 ) 假设我们有一个包含 n 项的数组：线性搜索最多比较元素多少次？
同样，同上，但现在'0(n)'似乎是这个问题的一般答案。再一次，我真的不明白这个答案背后的力量，并质疑为什么没有一些整数答案？
( 3 ) 有人可以解释一个线性搜索比二分搜索更好的例子吗？
从我收集到的信息来看，如果可能的话，二进制搜索通常似乎是更好的选择，因为它的速度很快。我无法确定线性搜索何时是更好的选择。
关于 1 和 2，如果提供绝对数字作为输入的大小，则绝对数字作为答案是可能的。由于问题询问的是任意大小的数组（长度 n），因此答案也以这些术语给出。
您可以阅读更多关于 big O notation 的详细信息，但基本上 O(n) 和 O(log n) 分别表示 order of n 和 order of log(n)。例如，如果输入大小为 100，则使用线性搜索的比较元素的数量也将在 100 的数量级，而使用二分搜索则需要比较 ~ log(100) 个元素。
至于3，二分查找需要对输入进行排序...
O 表示法是关于限制行为的。因此，二分查找将列表一分为二。要么您已经找到该项目，要么您有一半要搜索。因此 O(nlogn) 的限制行为 - 即在搜索树的叶子处。
线性搜索从头开始。最坏的情况（极限）是元素在最后）。
对于 (3)，如果该项目是列表中的第一个，那么您就中奖了。所以在那种情况下会更好
下面video提供了全面的解释。我希望它能帮助您理解二进制搜索和线性搜索之间的区别。
对于问题 3：
- 二进制搜索需要，排序序列。
- 对于序列 1,2,3,...,100。当要查找元素 1 时，线性搜索会更快。它只会检查第一个元素。
首先，您正在处理 O 表示法，因此 "whole number" 是不可能的。答案始终采用 O(f(n)) 格式，其中 f(n) 是 n 的某个函数。如果您不确定大 O 表示法是什么，那么从 http://en.wikipedia.org/wiki/Big_O_notation 开始可能会有帮助。
(1) 对排序数组进行二分查找，查找space 重复减半，直到找到元素。如果我们考虑一个理想的二进制搜索实现，其中每个操作都需要常数时间，在最坏的情况下，我们将需要检查大约 logn 个项目——这将花费 O(logn) 时间。至于 logn 背后的数学：它们并不难，但很难在 iPhone 上打出来。提示：Google 是你的朋友。
(2) 在未排序数组的线性搜索中，我们可能必须检查数组中的每一项。同样，这是一种简化，但假设我们算法中的每个操作都需要常数时间，我们必须至少查看 n 次。因此 O(n).
(3) (1) 和(2) 中必须搜索的数据有何不同？请记住，最佳排序是 O(nlogn).