python基础（六）查找方法

一、查找

查找，就是在一个数组（在 Python 中通常是 list）中，寻找某个特定的元素，并判断它是否在数组中，以及如果在，它的位置（下标）是多少。

例如，在列表 [2, 4, 6, 8] 中查找数字 6。

二、查找方法

1）最简单的查找方式：in

用python内置函数in可以快速判断该元素是否在数组中：

arr = [2, 4, 6, 8]

if 6 in arr:
print("找到了")
else:
print("没找到")

时间复杂度：O(n)

这种查找方法的优点是简单，但是无法通过这种方法知道元素的下标。

2）查找元素的位置：index()

另一个内置函数index()可以返回元素在数组中的下标：

arr = [2, 4, 6, 8]

index = arr.index(6)
print(index) # 2

但是，如果元素不存在， arr.index()就会报错。

因此，index()常和in搭配使用：

if 6 in arr:
index = arr.index(6)

3）线性查找（Linear Search）：for 循环查找

线性查找是一种最基础的查找方式，即将数组从第一个元素开始遍历，直到找到了目标值为止。一般在编写线性查找的代码时，我们会使用循环：

arr = [2, 4, 6, 8]
target = 6
index = -1

for i in range(len(arr)):
if arr[i] == target:
index = i
break

4）二分查找（Binary Search）：提高效率

二分查找有一个非常重要的前提：列表必须是有序的（升序或降序）

这个查找方法的核心思想是每次排除一半的数据

查找过程（假设数组是升序排序）：

时间复杂度：O(log n)

因此，每一次查找，范围都会缩小一半，这也就是二分查找速度快的原因。

为了方便大家理解二分查找的原理，我把手写二分查找的代码放在这里：

arr = [2, 4, 6, 8, 10]
target = 6

low = 0
high = len(arr) – 1
index = -1

while low <= high:
mid = (low + high) // 2
if arr[mid] > target:
high = mid – 1
elif arr[mid] < target:
low = mid + 1
else:
index = mid
break

除了手写之外，python有二分查找的内置函数bisect方便大家使用：

import bisect

arr = [2, 4, 6, 8, 10]
target = 6

index = bisect.bisect_left(arr, target)

if index < len(arr) and arr[index] == target:
print("找到了，下标是", index)
else:
print("没找到")