二分法查找有序数组中对应数据的索引
1 问题
在有序（升序或降序）的数组中查找对应数据的索引时，通常采取循环暴力求解：遍历数组中全部数据，直到数据等于目标值时，返回目标值的索引。但是，当数组中的数据足够多时，暴力求解会占用大量的时间。那么，该如何减少查找过程中所花费的时间呢？
2 方法
可以通过“二分法”减少查找过程中所花费的时间，二分法其数学解释为：对于区间[a，b]上连续不断且f(a)*f(b)<0的函数y=f(x)，通过不断地把函数f(x)的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫二分法。
简单来说，就是把需要查询的数据其所在的区间逐渐缩小，直到区间内只有需要的数据。不断把查询的区间对半缩小，避免无用功。这样可以节省大量的时间。
代码清单 1
# 以下内容为传统暴力求解# 查找所用的时间：0.9413014999990992simport timel = []for i in range(1,10000000): l.append(i)target = 35614 # 目标值start_time = time.perf_counter()for j in l: # for 循环暴力求解 if j == target: print(f'所在位置的下标：{l.index(j)}')end_time = time.perf_counter()time = end_time - start_timeprint(f'用时：{time}s')'''输出的结果：所在位置的下标：35613用时：0.9413014999990992s'''# 以下内容为二分法求解# 查找所花费的时间：0.0002653999999893131simport timel = []for i in range(1,10000000): l.append(i)target = 35614 # 目标值start_time = time.perf_counter()left = 0 # 左指针right = len(l) - 1 # 右指针while left <= right: # 设置循环，二分求解 mid = (left + right)//2 # 寻找中间值 if l[mid] == target: # 跳出循环的条件是找到了目标值 print(f'所在位置的下标：{mid}') break elif l[mid] < target: # 中间值作为左指针 left = mid + 1 elif l[mid] > target: # 中间值作为右指针 right = mid - 1end_time = time.perf_counter()time = end_time - start_timeprint(f'用时：{time}s')'''输出结果：所在位置的下标：35613用时：0.0002653999999893131s''' |
|---|
3 结语
在有序（升序或降序）的数组中查找对应数据的索引，当数组中的数据过多时，可以使用“二分法”优化查找所花费的时间。经过测试，使用time()模块统计程序运行时所花费的时间后，发现使用“二分法”查找比暴力查找快了3500倍之多，证明该方法是有效的。
腾讯云开发者
