C++实现二分查找：理解数组参数与指针的关系

"c++数据结构---二分查找" 在C++编程中，二分查找是一种高效的算法，常用于已排序的数据集。该算法通过不断缩小查找范围来定位目标值，其基本思想是每次比较中间元素与目标值，然后根据比较结果决定是在左半部分还是右半部分继续查找。这个过程一直持续到找到目标值或者搜索范围为空。 在这个例子中，我们有两个版本的`eFenChaZhao`函数，它们的主要区别在于参数的顺序。虽然在C++中，数组作为函数参数时会自动退化为指针，但函数的参数顺序不同可能会导致混淆。第一个函数定义为`int eFenChaZhao(int *arr, int lo, int k)`，而第二个版本交换了数组和长度的位置，即`int eFenChaZhao(int lo, int *arr, int k)`。在这两种情况下，`arr`都是数组的首地址，`lo`表示数组的长度，`k`是要查找的元素。 `eFenChaZhao`函数的实现遵循了经典的二分查找算法： 1. 初始化两个指针`low`和`high`，分别表示当前查找范围的起始和结束索引。 2. 在`while`循环中，只要`low`不大于`high`，就执行以下步骤： - 计算中间索引`mid`，即`low`和`high`的平均值向下取整。 - 检查中间元素`arr[mid]`是否等于目标值`k`，如果相等则返回`mid`作为结果。 - 如果中间元素大于目标值，那么目标值可能在左半部分，将`high`更新为`mid - 1`。 - 否则，目标值可能在右半部分，将`low`更新为`mid + 1`。 3. 当`while`循环结束后，如果未找到目标值，则返回0表示失败。 在`main`函数中，首先创建了一个整数数组`a`，并计算了它的长度`lo`。然后调用`eFenChaZhao`函数寻找数值66的位置。注意这里可以灵活地调整函数参数的顺序，因为数组作为参数会自动转换为指针。如果函数返回0，表示未找到目标值；否则，输出66所在的索引位置。 为了提高代码可读性和效率，可以对`eFenChaZhao`函数进行一些改进，例如： 1. 使用类型安全的`size_t`类型表示数组长度，避免可能出现的整数溢出问题。 2. 考虑边界情况，如当查找长度为0时，应该直接返回0，无需进行查找。 3. 在查找过程中，可以考虑在找到目标值后立即跳出循环，避免不必要的比较。 改进后的代码可能如下所示： ```cpp #include <iostream> #include <cstddef> int eFenChaZhao(int *arr, size_t lo, int k) { if (lo == 0) return 0; size_t low = 0, high = lo - 1; while (low <= high) { size_t mid = low + (high - low) / 2; if (arr[mid] == k) { return mid; } else if (arr[mid] > k) { high = mid - 1; } else { low = mid + 1; } } return 0; } int main() { int a[] = {11, 2, 4, 35, 5, 66, 100, 22, 369, 1588, 89}; size_t lo = sizeof(a) / sizeof(a[0]); std::cout << "数组长度：" << lo << std::endl; int p = eFenChaZhao(a, lo, 66); if (p == 0) { std::cout << "找不到！！！" << std::endl; } else { std::cout << "66所在的位置：" << p << std::endl; } return 0; } ``` 这样的改进使代码更加健壮，同时保持了二分查找算法的核心效率。在实际应用中，二分查找算法不仅适用于静态数组，还可以应用于动态数据结构，如平衡二叉搜索树或某些支持高效随机访问的操作系统内核数据结构。