4.1 线性搜索和二分搜索的时间复杂度比较
让我们来比较一下线性搜索和二分搜索的时间复杂度。
线性搜索：
- 时间复杂度：
O(n)，其中n是数组或列表中的元素数量。 - 最佳情况：
O(1)— 元素在第一个位置找到。 - 平均情况：
O(n/2) = O(n)— 元素在中间某处找到。 - 最坏情况：
O(n)— 元素在最后一个位置找到或不存在。
二分搜索：
- 时间复杂度：
O(log n)，其中n是数组或列表中的元素数量。 - 最佳情况：
O(1)— 元素在第一步找到（中间元素）。 - 平均情况：
O(log n)— 在已排序数组中查找。 - 最坏情况：
O(log n)— 元素在最后一步找到或不存在。
时间复杂度分析示例
线性搜索：
- 数组
[1, 3, 5, 7, 9, 11, 13]，目标元素是 7。 - 检查每个元素直到在索引 3 找到 7。
- 需要 4 次检查，符合
O(n)。
二分搜索：
- 数组
[1, 3, 5, 7, 9, 11, 13]，目标元素是7。 - 中间元素（7）在第一步找到。
- 需要 1 次检查，符合
O(log n)。
4.2 每种方法的优缺点
让我们看看每种搜索类型的优点和缺点。
线性搜索：
优点：
- 实现简单：线性搜索非常容易实现和理解。
- 无需数据排序：可以对未排序的数据使用线性搜索。
- 适合小型数组：线性搜索在小型数组中是高效的。
缺点：
- 大数组中效率低下：时间复杂度
O(n)使其在大数组中效率低下。 - 执行时间长：对于大数组，线性搜索可能需要很长时间，特别是在目标元素位于数组末尾或不存在的情况下。
二分搜索：
优点：
- 大数组中效率高：时间复杂度
O(log n)使其在大数组中非常高效。 - 快速执行：在处理大规模排序数组时，二分搜索比线性搜索快得多。
缺点：
- 需要排序数据：二分搜索仅适用于排序数组，这可能需要额外时间进行预排序。
- 实现复杂：与线性搜索相比，二分搜索的实现更复杂。
4.3 何时使用哪种搜索
来看看什么时候使用线性搜索，什么时候使用二分搜索。
线性搜索。
在以下情况下使用线性搜索：
- 数组或列表未排序。
- 数组或列表的大小较小。
- 需要简单和快速的解决方案，而无需额外的排序开销。
- 需要找到元素的第一个出现位置或所有出现位置。
- 数据是实时到达的，预排序是不可能或不合适的。
二分搜索。
在以下情况下使用二分搜索：
- 数组或列表已排序。
- 数组或列表的大小很大。
- 在同一数据集中频繁搜索元素（可以将数据预排序一次）。
- 搜索速度很重要。
- 可以花时间预排序数据。
4.4 线性搜索的示例任务
1. 在未排序列表中搜索
需要在未排序的数字列表中找到指定数字的索引。
示例：
def linear_search(arr, target):
for index, element in enumerate(arr):
if element == target:
return index
return -1
arr = [4, 2, 7, 1, 9, 3]
target = 7
print(linear_search(arr, target)) # 输出: 2
2. 在数组中搜索第一次出现
需要在字符串列表中找到指定元素的第一次出现。
示例：
def linear_search(arr, target):
for index, element in enumerate(arr):
if element == target:
return index
return -1
words = ["apple", "banana", "cherry", "date", "banana"]
target = "banana"
print(linear_search(words, target)) # 输出: 1
3. 在实时数据中搜索
在实时到达的数据流中找到元素。
示例：
import random
def find_in_stream(stream, target):
for index, element in enumerate(stream):
if element == target:
return index
return -1
stream = [random.randint(1, 100) for _ in range(100)]
target = 50
print(find_in_stream(stream, target))
4.5 二分搜索的示例任务
1. 在已排序数组中搜索
需要在已排序的数字数组中找到指定数字的索引。
示例：
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(sorted_array, target)) # 输出: 3
2. 在大型数据集中频繁搜索
频繁在大型已排序数字数组中搜索元素。
示例：
import random
sorted_large_array = sorted([random.randint(1, 1000000) for _ in range(1000000)])
target = random.choice(sorted_large_array)
print(binary_search(sorted_large_array, target))
3. 在已排序的数据库中搜索元素
根据关键字段在已排序的数据库中查找记录。
示例：
database = sorted([{"id": i, "value": f"record_{i}"} for i in range(100000)])
def binary_search_db(db, target_id):
left, right = 0, len(db) - 1
while left <= right:
mid = (left + right) // 2
if db[mid]["id"] == target_id:
return db[mid]
elif db[mid]["id"] < target_id:
left = mid + 1
else:
right = mid - 1
return None
target_id = 54321
print(binary_search_db(database, target_id))
GO TO FULL VERSION