我在 C++ 中运行二进制搜索算法,但它给了我虚假的结果。例如,搜索值 21 会得到一个
"Value is Found"
消息,但我的数组只包含从 0 到 20 的数字。
非常感谢任何帮助。
#include <iostream>
#include <iomanip>
using namespace std;
int binarySearch(const int [], int, int, int, int ); // function prototype
int main()
{
const int arraySize = 10;
int arr[ arraySize ];
int key;
for( int i = 0; i <= arraySize; i++) // generate data for array
arr[i] = 2*i;
cout << "The array being searched is: " << endl;
for (int j = 0; j<=arraySize; j++) // print subscript index of the array
{
cout << setw(5) << j << " ";
}
cout << endl;
for (int z = 0; z<=arraySize; z++) // print elements of the array below index
{
cout << setw(5) << arr[z] << " ";
}
cout << "\n" <<"Enter value you want to search in array " << endl;
cin >> key;
int result = binarySearch(arr, key, 0, arraySize, arraySize); // function call
if (result == 1) // print result of search
cout << "Key is found " << endl;
else
cout << "Key not found " << endl;
return 0;
} // end main function
int binarySearch(const int a[], int searchKey, int low, int high, int length)
{
int middle;
while (low <= high){
middle = (low + high) / 2;
if (searchKey == a[middle]) // search value found in the array, we have a match
{
return 1;
break;
}
else
{
if( searchKey < a[middle] ) // if search value less than middle element
high = middle - 1; // set a new high element
else
low = middle + 1; // otherwise search high end of the array
}
}
return -1;
}
最佳答案
您正在调用 undefined behavior因为你的for
循环条件是 <=arraySize
.将其更改为 <arraySize
.进行此更改后,代码非常适合样本输入。
写int arr[ arraySize ];
您正在创建一个包含 10 个元素的数组(即从 0
到 9
),而在 for 循环中,您从 0
开始并移动到 10
.
关于C++ 二进制搜索无法正常工作 - 查找不在数组中的元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37227125/