首页 > 日常生活->二分查找的非递归算法代码（二分搜索的非递归实现）

二分查找的非递归算法代码（二分搜索的非递归实现）

biubiu+ 论文 2023-12-19 15:58:32 8549 次浏览评论已关闭

二分搜索的非递归实现

介绍

二分搜索是高效的搜索算法之一，它能够从有序的线性数据结构中寻找目标值。当数据集合较大时，它优于线性搜索，因为它的时间复杂度为 O(log n) 而不是 O(n)。本文将会介绍二分搜索的非递归实现方法以C++为例。

算法原理

二分搜索需要将目标元素与数据集合的中点相比较。如果目标元素比中点小，则把区间缩小为左半部分（数组的左边），否则缩小为右半部分（数组的右边）。重复此过程，直到找到目标或区间为空，这被认为是一种分治算法。

代码实现

二分查找的非递归算法代码（二分搜索的非递归实现）

```c++#include #include int binary_search(std::vector arr, int target){ int low = 0; int high = arr.size() - 1; while (low <= high) { int mid = low + ((high - low) / 2); if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } } return -1; // 如果搜索失败，返回-1}int main(){ std::vector arr = {1, 3, 5, 7, 9}; int target = 7; int result = binary_search(arr, target); if (result == -1) { std::cout << \"搜索失败\" << std::endl; } else { std::cout << \"目标元素在数组中的位置为：\" << result << std::endl; } return 0;}```

分析

- 首先要将搜索区间确定在 low 和 high 之间，这里的初始 low 等于 0，high 等于数组大小减 1。- 然后在每次循环开始时都要重新计算 mid，以保证 mid 始终是有效的。这里使用 high - low 避免使用 (low + high) / 2 时可能发生的上溢出错误。- 然后比较arr [mid]和目标值。如果它们相等，则返回mid，表示已找到目标值。- 如果目标小于中点值，则缩小区间到左侧的子区间；否则缩小区间到右侧的子区间。由于我们已经比较过了中点处的值，因此搜索范围不包括中点本身。- 如果没有找到目标，重复此过程，直到区间为空为止。如果在循环结束时还没有找到目标，则搜索失败，返回-1。

总结

二分查找的非递归算法代码（二分搜索的非递归实现）