二分搜索与顺序搜索

Question

对于这些特定情况，在二进制搜索（需要首先排序）上使用顺序搜索更好的数组大小。第一种情况是数组的所有值都只是随机数而不是排序。第二种情况是数组的值或随机数按数字从最小到最大或从最大到最小排序。对于搜索，假设您只想在数组中找到一个数字。

案例 1：随机数

案例2：已经排序

Answer 1

顺序搜索算法的最坏情况运行时间为 O(n)，并且不依赖于数据是否已排序。二分搜索算法的最坏情况运行时间为 O(logn)，但是，为了使用算法，必须对数据进行排序。如果数据没有排序，排序数据将花费 O(nlogn) 时间。所以：情况 1：当数据未排序时，顺序搜索将更省时，因为它需要 O(n) 时间。二分搜索需要将数据按 O(nlogn) 排序，然后搜索 O(logn)。因此，时间复杂度为 O(nlogn) + O(logn) = O(nlogn)。情况 2：当数据被排序时，二分搜索会更省时，因为它只需要 O(logn) 时间，而顺序搜索仍然需要 O(n) 时间。

Answer 2

二分查找总是更好。但是二分查找总是要求对数组进行排序。