线性查找与二分查找

什么是线性查找？

线性查找（Linear Search）是一种简单直观的搜索算法。它通过遍历数组中的每个元素来检查给定值是否存在于该数组中。在最坏的情况下，需要遍历整个数组才能确定目标是否存在。

算法流程

1. 初始化一个索引变量 i 为0。
2. 遍历数组中的每一个元素，比较当前元素与要查找的值。
3. 如果找到匹配项，则返回该元素的索引。
4. 如果遍历完所有元素都没有找到匹配项，则返回未找到信息。

示例代码

def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

# 测试线性查找
arr = [10, 20, 80, 30, 60, 50, 110, 100, 130, 170]
x = 110
result = linear_search(arr, x)
if result != -1:
    print("元素在数组中的索引为:", result)
else:
    print("元素不在数组中")

什么是二分查找？

二分查找（Binary Search）是一种高效的搜索算法，它依赖于数组或列表有序的性质。通过每次将查找范围减半来快速定位目标值的位置。

算法流程

1. 初始化两个变量 low 和 high 分别为数组的第一个元素索引和最后一个元素索引。

2. 当 low 小于等于 high 时，进行以下操作：

   • 计算中间位置 mid。
   • 比较中间位置的值与目标值：
     • 如果相等，则返回 mid。
     • 如果目标值小于中间位置的值，则在左侧子数组中继续查找。
     • 否则，在右侧子数组中继续查找。

3. 遍历完所有元素仍未找到匹配项，则返回未找到信息。

示例代码

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1

    return -1

# 测试二分查找
arr = [10, 20, 30, 40, 50]
x = 30
result = binary_search(arr, x)
if result != -1:
    print("元素在数组中的索引为:", result)
else:
    print("元素不在数组中")

性能比较

• 线性查找：时间复杂度为 O(n)，需要检查数组的每个元素。
• 二分查找：时间复杂度为 O(log n)，适用于已排序的数据结构，速度远快于线性查找。

使用场景

• 线性查找适合小规模或未排序数据集。
• 二分查找更适合大规模有序数组或列表。

通过选择合适的查找算法，可以有效提高程序的执行效率。