Python二分查找算法：在有序数组中查找指定数字

本篇博客将介绍如何使用Python实现二分查找算法，并提供一个完整的示例代码，演示如何在升序排序的100个随机整数（1～1000）数列中查找某个数，并输出其位置。

什么是二分查找？

二分查找是一种高效的搜索算法，用于在已排序的数据集中查找特定元素。它的工作原理是：

比较目标值与数组中间元素。 2. **如果目标值等于中间元素，则返回中间元素的索引。**3. **如果目标值小于中间元素，则在数组的左半部分继续搜索。**4. 如果目标值大于中间元素，则在数组的右半部分继续搜索。

**代码示例:**pythonimport random

生成升序排序的100个随机整数数列numbers = sorted(random.sample(range(1, 1001), 100))

二分法查找函数def binary_search(numbers, target): low = 0 high = len(numbers) - 1

while low <= high:        mid = (low + high) // 2        if numbers[mid] == target:            return mid        elif numbers[mid] < target:            low = mid + 1        else:            high = mid - 1

return -1

需要查找的数target = random.randint(1, 1000)

使用二分法查找并输出结果result = binary_search(numbers, target)if result != -1: print(f'数列中的数 {target} 位于第 {result+1} 个位置。')else: print(f'数列中的数 {target} 不存在。')

代码解释:

首先，我们使用random模块生成100个随机整数，并使用sorted()函数对其进行升序排序。2. 然后，我们定义了一个名为binary_search()的函数，它接受一个已排序的数组和一个目标值作为参数。3. 在函数内部，我们使用while循环不断缩小搜索范围，直到找到目标值或搜索范围为空。4. 在每次迭代中，我们计算中间元素的索引mid，并比较目标值与中间元素的值。5. 如果目标值等于中间元素，则返回中间元素的索引。6. 如果目标值小于中间元素，则将搜索范围缩小到左半部分，即将high设置为mid - 1。7. 如果目标值大于中间元素，则将搜索范围缩小到右半部分，即将low设置为mid + 1。8. 如果循环结束时仍未找到目标值，则返回-1，表示目标值不在数组中。

总结:

二分查找是一种高效的搜索算法，适用于已排序的数据集。通过不断缩小搜索范围，可以快速找到目标值或确定目标值不存在。