1 简介

这里介绍两种重要的搜索算法类型：线性搜索和二叉搜索。

2 线性搜索和二分查找的实现和复杂性分析

这里通过简单示例、代码实现和时间复杂度分析来详细讨论这两个问题。

3 线性或顺序搜索

工作原理是从一端按顺序遍历整个数组或列表，直到找到目标元素。

如果找到该元素，则返回其索引，否则返回 -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)

4 二分搜索

这种类型的搜索算法用于查找排序数组中包含的特定值的位置。二叉搜索算法遵循分而治之的原则，它被认为是最好的搜索算法，因为它运行速度更快。

现在让我们以一个排序数组为例，尝试了解它是如何工作的：

• 示例：

            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)