C++二进制搜索不能正常工作 - 查找元素不在数组

Question

我在C++中运行二分搜索算法，但它给了我虚假的结果。例如，搜索该值21给我一个

“值被找到”

消息，但我的阵列仅由数字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; 
} 

Answer 1

因为你for循环条件<=arraySize要调用undefined behavior。将其更改为<arraySize。在进行此更改时，代码完美适用于示例输入。

通过写int arr[ arraySize ];要创建10个元素（即，从0到9）的阵列，而在for循环，从0开始和移动，直到10。

Live Demo