求助:修正C++二分查找代码索引错误与数组越界问题
错误点明细
- 静态变长数组不合法:C++标准不允许使用变量作为长度声明静态数组,你先将size初始化为0后声明
myarr[size],数组实际长度固定为0,后续所有对数组的写入操作都会直接越界。 - 输入循环边界错误:输入数组元素的for循环条件写为
i <= size,会尝试读取size+1个元素,超出数组合法访问范围。 - 二分查找右边界传参错误:调用
binarySearch时传入的右边界为size,而有序数组的最大合法下标为size-1,会导致查找过程中访问越界,也会出现匹配到本不存在的下标、或找不到已存在元素的问题。 - 二分查找逻辑冗余:判断
arr[c] <= number时,等于的场景已经被前一个arr[c] == number条件覆盖,直接写arr[c] < number即可,不过该问题不影响运行结果,属于逻辑不严谨。 - 中点计算存在溢出风险:原代码用
(b+e)/2计算中点,当b和e的数值接近int类型上限时,b+e会出现整数溢出,导致中点计算错误。
修正后可用代码
#include <iostream> using namespace std; int binarySearch(int arr[], int b, int e, int number) { while (b <= e) { // 优化中点计算逻辑,避免整数溢出 int c = b + (e - b) / 2; if (arr[c] == number) { return c; } else if (arr[c] < number) { b = c + 1; } else { e = c - 1; } } return -1; } int main() { int size; // 先读取数组长度,再动态分配数组空间 cin >> size; int* myarr = new int[size]; int num; int output; // 修正循环边界,只读取size个元素 for (int i = 0; i < size; i++) { cin >> myarr[i]; } cin >> num; // 传入正确的右边界:数组最后一个元素的下标size-1 output = binarySearch(myarr, 0, size - 1, num); cout << output; // 释放动态分配的数组空间,避免内存泄漏 delete[] myarr; return 0; }
使用注意
二分查找要求输入的数组是升序有序的,如果输入数组无序,查找结果会不符合预期。
内容的提问来源于stack exchange,提问作者Keith
相关产品推荐
相关产品推荐

