查找算法

2023-06-26 16:09| 来源: 网络整理| 查看: 265

查找算法

查找算法是计算机科学中的一种常见算法，用于在数据集合中查找指定的元素或确定元素是否存在。查找算法可以应用于各种数据结构，如数组、链表、二叉搜索树等。它们的目标是通过有效地比较元素来最小化查找的时间复杂度。

以下是一些常见的查找算法：

线性查找（Linear Search）：线性查找是最简单的查找算法之一。它从数据集的起始位置开始逐个比较元素，直到找到目标元素或遍历完整个数据集。线性查找的时间复杂度为O(n)，其中n是数据集的大小。

二分查找（Binary Search）：二分查找要求数据集是有序的。它通过重复将数据集分成两半，并根据目标元素与中间元素的大小关系来确定目标元素在哪一半中。通过不断缩小搜索范围，最终可以找到目标元素或确定其不存在。二分查找的时间复杂度为O(log n)，其中n是数据集的大小。

顺序查找

时间复杂度： O ( n ) O(n) O(n)

def search(lst, val): for i, v in enumerate(lst): if val == v: return i return -1 arr = [5, 3, 7, 8, 0] print(search(arr, 99)) 二分查找(必须是有序)

时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)

# 二分查找只适用于在有序序列中查找元素 def binary_search(lst, val): left = 0 right = len(lst) - 1 while left val: # 说明要查找的值在mid的左边 right = mid - 1 else: # 说明要查找的值在mid的右边、 left = mid + 1 # 代码执行至此说明没有找到元素val，返回-1 return -1 # 注意：mid定义在while循环里面 arr = [1, 2, 4, 5, 7, 9] print(binary_search(arr,77))

【本文地址】

查找算法

查找算法

今日新闻

推荐新闻