二分法查找有序数组中对应数据的索引

Love The Way You Lie 2024-03-23 17:54 58阅读 0赞

**1** **问题**

在有序（升序或降序）的数组中查找对应数据的索引时，通常采取循环暴力求解：遍历数组中全部数据，直到数据等于目标值时，返回目标值的索引。但是，当数组中的数据足够多时，暴力求解会占用大量的时间。那么，该如何减少查找过程中所花费的时间呢？

**2** **方法**

可以通过“二分法”减少查找过程中所花费的时间，二分法其数学解释为：对于区间\[a，b\]上连续不断且f(a)\*f(b)<0的函数y=f(x)，通过不断地把函数f(x)的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫二分法。

简单来说，就是把需要查询的数据其所在的区间逐渐缩小，直到区间内只有需要的数据。不断把查询的区间对半缩小，避免无用功。这样可以节省大量的时间。

代码清单 1

<table> 
 <tbody> 
 <tr> 
 <td># 以下内容为传统暴力求解 # 查找所用的时间：0.9413014999990992s import time l = [] for i in range(1,10000000): &nbsp; &nbsp;l.append(i) target = 35614 # 目标值 start_time = time.perf_counter() for j in l: # for 循环暴力求解 &nbsp; &nbsp;if j == target: &nbsp; &nbsp; &nbsp; &nbsp;print(f'所在位置的下标：{l.index(j)}') end_time = time.perf_counter() time = end_time - start_time print(f'用时：{time}s') ''' 输出的结果： 所在位置的下标：35613 用时：0.9413014999990992s ''' # 以下内容为二分法求解 # 查找所花费的时间：0.0002653999999893131s import time l = [] for i in range(1,10000000): &nbsp; &nbsp;l.append(i) target = 35614 # 目标值 start_time = time.perf_counter() left = 0 # 左指针 right = len(l) - 1 # 右指针 while left &lt;= right: # 设置循环，二分求解 &nbsp; &nbsp;mid = (left + right)//2 # 寻找中间值 &nbsp; &nbsp;if l[mid] == target: # 跳出循环的条件是找到了目标值 &nbsp; &nbsp; &nbsp; &nbsp;print(f'所在位置的下标：{mid}') &nbsp; &nbsp; &nbsp; &nbsp;break &nbsp; &nbsp;elif l[mid] &lt; target: # 中间值作为左指针 &nbsp; &nbsp; &nbsp; &nbsp;left = mid + 1 &nbsp; &nbsp;elif l[mid] &gt; target: # 中间值作为右指针 &nbsp; &nbsp; &nbsp; &nbsp;right = mid - 1 end_time = time.perf_counter() time = end_time - start_time print(f'用时：{time}s') ''' 输出结果： 所在位置的下标：35613 用时：0.0002653999999893131s '''</td> 
 </tr> 
 </tbody> 
</table>

**3** **结语**

在有序（升序或降序）的数组中查找对应数据的索引，当数组中的数据过多时，可以使用“二分法”优化查找所花费的时间。经过测试，使用time()模块统计程序运行时所花费的时间后，发现使用“二分法”查找比暴力查找快了3500倍之多，证明该方法是有效的。