1 两个重要的基础搜索算法
本文探讨了两种搜索算法：线性搜索和二分查找。
这里通过简单示例、代码实现和时间复杂度分析来详细讨论这两个问题。
2 线性或顺序搜索
工作原理是从一端按顺序遍历整个数组或列表，直到找到目标元素。
如果找到该元素，则返回其索引，否则返回 -1。
示例：
arr = [6, 12, 15, 11, 9, 19, 49]
我们需要找到 9 的索引。
实现：
def search(nums, target):
for i in range(len(nums)):
if nums[i] == target:
return i
return -1
if __name__ == '__main__':
nums = [2, 12, 15, 11, 7, 19, 45]
target = 7
print(search(nums, target))
步骤：
1 从索引 0 开始，并将每个元素与目标进行比较。
2 如果发现目标等于元素，则返回其索引。
3 如果未找到目标，则返回 -1。
复杂度
当目标元素是数组的第一个元素时，会出现最佳情况。在本例中，比较次数为 1。因此，时间复杂度为 。O(1)
平均情况： 平均而言，目标元素将位于数组的中间位置。在这种情况下，比较次数将为 N/2。因此，时间复杂度将是（常量被忽略） O(N)
当目标元素是数组中的最后一个元素或不在数组中时，会发生最坏的情况。在这种情况下，我们必须遍历整个数组，因此比较次数将为 N。因此，时间复杂度将是 O(N)
3 二分搜索
这种类型的搜索算法用于查找排序数组中包含的特定值的位置。二叉搜索算法遵循分而治之的原则，它被认为是最好的搜索算法，因为它运行速度更快。
现在让我们以一个排序数组为例，尝试了解它是如何工作的：
示例：
arr = [6, 12, 15, 17, 29, 39, 49]
假设要搜索的目标元素是 17
- 二分查找的方法
1 将目标元素与数组的中间元素进行比较。
2 如果目标元素大于中间元素，则搜索在右半部分继续。
3 否则，如果目标元素小于中间值，则在左半部分继续搜索。
4 重复此过程，直到中间元素等于目标元素，或者目标元素不在数组中。
5 如果找到目标元素，则返回其索引，否则返回 -1。
代码实现
def search(nums, target): start = 0 end = len(nums)-1 is_ascending = nums[start] < nums[end] while start <= end: mid = start + (end-start)//2 if target == nums[mid]: return mid if is_ascending: if target < nums[mid]: end = mid-1 else: start = mid+1 else: if target < nums[mid]: start = mid+1 else: end = mid-1 return -1 if __name__ == '__main__': nums1 = [-1, 2, 4, 6, 7, 8, 12, 15, 19, 32, 45, 67, 99] nums2 = [99, 67, 45, 32, 19, 15, 12, 8, 7, 6, 4, 2, -1] target = -1 print(search(nums1, target)) print(search(nums2, target))
- 复杂度分析
当目标元素是数组的中间元素时，会出现最佳情况。
在本例中，比较次数为 1。因此，时间复杂度为O(1)。
平均情况：平均而言，目标元素将位于数组中的某个位置。
因此，时间复杂度将是O(logN)
当目标元素不在列表中或远离中间元素时，会发生最坏情况。
因此，时间复杂度将是O(logN)
