二分查找算法举例说明（二分查找算法例题）

# 简介在计算机科学中，二分查找（Binary Search）是一种高效的查找算法，它适用于有序数组。二分查找通过反复将搜索区间减半来快速定位目标值的位置。这种算法的时间复杂度为O(log n)，比线性查找的O(n)要高效得多。本文将详细介绍二分查找的工作原理，并通过具体例子进行说明。# 二分查找的基本概念## 定义 二分查找算法通过比较目标值与中间元素的大小，然后决定下一步搜索的方向。如果目标值等于中间元素，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找。## 工作原理 1. 初始化左右指针：`left = 0`，`right = len(array) - 1` 2. 计算中间索引：`mid = (left + right) // 2` 3. 比较中间元素与目标值：- 如果 `array[mid] == target`，查找成功。- 如果 `array[mid] < target`，则在右半部分继续查找。- 如果 `array[mid] > target`，则在左半部分继续查找。 4. 重复步骤2和3，直到找到目标值或搜索区间为空。# 二分查找算法示例## 示例数据 假设我们有一个有序数组 `[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]`，我们要在这个数组中查找目标值 `13`。## 算法实现 ```python def binary_search(array, target):left, right = 0, len(array) - 1while left <= right:mid = (left + right) // 2if array[mid] == target:return midelif array[mid] < target:left = mid + 1else:right = mid - 1return -1 # 表示未找到目标值# 测试 array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] target = 13 result = binary_search(array, target) if result != -1:print(f"Element found at index {result}") else:print("Element not found") ```## 运行过程分析 1. 初始化：`left = 0`, `right = 9` 2. 第一次迭代：- `mid = (0 + 9) // 2 = 4`- `array[4] = 9`，`9 < 13`，因此在右半部分继续查找。 3. 第二次迭代：- `left = 5`, `right = 9`- `mid = (5 + 9) // 2 = 7`- `array[7] = 15`，`15 > 13`，因此在左半部分继续查找。 4. 第三次迭代：- `left = 5`, `right = 6`- `mid = (5 + 6) // 2 = 5`- `array[5] = 11`，`11 < 13`，因此在右半部分继续查找。 5. 第四次迭代：- `left = 6`, `right = 6`- `mid = (6 + 6) // 2 = 6`- `array[6] = 13`，`13 == 13`，查找成功。最终结果为 `Element found at index 6`。# 总结 二分查找是一种非常高效的查找算法，特别适合于大规模数据的查找。通过不断缩小搜索范围，可以显著提高查找效率。希望本文通过具体的例子和代码展示了二分查找的基本工作原理及其应用。

简介在计算机科学中，二分查找（Binary Search）是一种高效的查找算法，它适用于有序数组。二分查找通过反复将搜索区间减半来快速定位目标值的位置。这种算法的时间复杂度为O(log n)，比线性查找的O(n)要高效得多。本文将详细介绍二分查找的工作原理，并通过具体例子进行说明。

二分查找的基本概念

定义 二分查找算法通过比较目标值与中间元素的大小，然后决定下一步搜索的方向。如果目标值等于中间元素，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找。

工作原理 1. 初始化左右指针：`left = 0`，`right = len(array) - 1` 2. 计算中间索引：`mid = (left + right) // 2` 3. 比较中间元素与目标值：- 如果 `array[mid] == target`，查找成功。- 如果 `array[mid] < target`，则在右半部分继续查找。- 如果 `array[mid] > target`，则在左半部分继续查找。 4. 重复步骤2和3，直到找到目标值或搜索区间为空。

二分查找算法示例

示例数据 假设我们有一个有序数组 `[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]`，我们要在这个数组中查找目标值 `13`。

算法实现 ```python def binary_search(array, target):left, right = 0, len(array) - 1while left <= right:mid = (left + right) // 2if array[mid] == target:return midelif array[mid] < target:left = mid + 1else:right = mid - 1return -1

表示未找到目标值

测试 array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] target = 13 result = binary_search(array, target) if result != -1:print(f"Element found at index {result}") else:print("Element not found") ```

运行过程分析 1. 初始化：`left = 0`, `right = 9` 2. 第一次迭代：- `mid = (0 + 9) // 2 = 4`- `array[4] = 9`，`9 < 13`，因此在右半部分继续查找。 3. 第二次迭代：- `left = 5`, `right = 9`- `mid = (5 + 9) // 2 = 7`- `array[7] = 15`，`15 > 13`，因此在左半部分继续查找。 4. 第三次迭代：- `left = 5`, `right = 6`- `mid = (5 + 6) // 2 = 5`- `array[5] = 11`，`11 < 13`，因此在右半部分继续查找。 5. 第四次迭代：- `left = 6`, `right = 6`- `mid = (6 + 6) // 2 = 6`- `array[6] = 13`，`13 == 13`，查找成功。最终结果为 `Element found at index 6`。

总结 二分查找是一种非常高效的查找算法，特别适合于大规模数据的查找。通过不断缩小搜索范围，可以显著提高查找效率。希望本文通过具体的例子和代码展示了二分查找的基本工作原理及其应用。