GCSE 计算机科学/搜索算法
如果您有一个未排序的列表（或数组），那么最简单的搜索算法是线性搜索。它逐个遍历列表项，并与要搜索的项进行比较。如果比较成功，则算法已找到该项。如果所有比较都失败，则该项不存在于数组或列表中。在最简单的变体中，算法返回一个布尔值以指示成功或失败。
|
练习：线性搜索 考虑字符串列表“Cat”、“Mouse”、“Frog”、“Lion”、“Panda”、“Llama”、“Bee”，按此顺序。找到“Panda”需要多少次比较？ 答案 5 当搜索“Camel”时需要多少次比较？ 答案 需要 7 次比较才能得出该字符串不在列表中的结论。 |
正如上一个问题所指出的，线性搜索可能需要与列表中项目数量一样多的比较，因此在数百万个名字列表（例如一个国家的选民登记册）中搜索一个名字可能需要很长时间。
如果您的列表按升序排序，或者通过排序算法按升序排序，那么您可以执行二分搜索。这涉及在每次比较时将数据分成两半，从而更快地“缩小”到项目必须存在于列表中的部分，如果它存在于列表中。这会导致更好的性能。
- 让我们在以下排序列表中搜索名字 Miles
- Ali, Bernie, Claire, Mohammed, Peter, Simon, Yvonne
- 我们将 Miles 与中间的名字 Mohammed 进行比较
- Ali, Bernie, Claire, Mohammed, Peter, Simon, Yvonne
- Miles 按字母顺序排在 Mohammed 之前，因此我们知道 Miles 不会出现在 Mohammed 的右边。因此，我们可以“丢弃”列表的右半部分
- Ali, Bernie, Claire,
Mohammed, Peter, Simon, Yvonne
- 现在我们将 Miles 与剩余列表中的中间名字 Bernie 进行比较
- Ali, Bernie, Claire,
Mohammed, Peter, Simon, Yvonne
- Miles 按字母顺序排在 Bernie 之后，所以我们可以丢弃左边
Ali, Bernie, Claire,Mohammed, Peter, Simon, Yvonne
- 最后，我们将 Miles 与这个单项列表的中间名字 Claire 进行比较
Ali, Bernie, Claire,Mohammed, Peter, Simon, Yvonne
- Miles 与 Claire 不一样，没有更多项可以比较，所以我们知道 Miles 不在列表中。
这仅使用二分搜索进行了 3 次比较，使用线性搜索则需要 7 次比较。当列表很大时，情况会更好。例如，一个包含 1,000,000,000 个项目的列表，使用二分搜索最多只需要 30 次比较！拥有排序数据非常有用。
|
练习：线性搜索与二分搜索 排序数据对线性搜索也很有用。修改后的线性搜索算法如何在搜索 Miles 时进行少于 7 次比较？ 答案 修改后的线性搜索将在 4 次比较后（与 Ali、Bernie、Claire 和 Mohammed 比较）知道 Miles 不在排序列表中，因为 Miles 应该出现在 Mohammed 之前。 对于上面显示的 7 个名字的列表，你能想到线性搜索比二分搜索更快的案例吗？ 答案 如果我们搜索列表中的第一个项目 Ali，二分搜索仍然需要 3 次比较（与 Mohammed、Bernie 和 Ali 比较），但线性搜索只需要 1 次比较。 对于大型列表的线性搜索，最佳情况是所搜索的项目在第一个位置。大型列表的二分搜索的最佳情况是什么？ 答案 如果所搜索的项目位于列表的中间，则二分搜索只需要 1 次比较。 |
二分搜索在排序数组中定位项目的所在位置。每次比较失败后，二分搜索都会将搜索空间减少一半。它的效率如何？对于 x 个项目的搜索次数是多少？公式是什么？为什么它比线性搜索更好。
如何计算 x 大小数组上的最大搜索次数 (n)
2^n > size of list (x) where n = max searches
例如，如果我们有一个 3 个项目的数组
2^2 = 4 > 3 therefore max searches = 2
|
练习：二分搜索 给定一个包含 256 个项目的排序列表，找到一个项目所需的最大搜索次数是多少？
答案 9 as: 给定一个包含 1000 个项目的排序列表，找到一个项目所需的最大搜索次数是多少？
答案 10 as: 2^n > size of list where n = max searches 2^10 = 1024 > 1000 |