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に変更してください。この変更を加えると、コードはサンプル入力に対して完全に機能します。

にforループ、あなたが0から開始し10まで移動しているときに、10の要素（すなわち、0から9まで）の配列を作成しているint arr[ arraySize ];書き込むことによって。一度に、あなたのコードを1行をステップデバッガを使用

Live Demo