C++ Binary Search Not Working Correctly - Finds Element Not in Array

Question

I am running the binary search algorithm in C++ but it gives me spurious results. For example, searching for the value 21 gives me a

"Value is Found"

message but my array consists only of numbers from 0 to 20.

Any help is greatly appreciated.

#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;
}

• Sam Varshavchik: When you used your debugger to step through your code, one line at a time, what did your debugger tell you is the reason your code produced the wrong result?
• Alan Stokes: Is your array sorted?
• quidproquo: I went through line by line and could not see the issue, but I think the answer is the as per CodingBatman's answer below.

Answer 1

You are invoking undefined behavior because your for loop conditions are <=arraySize. Change it to <arraySize. On making this change, the code works perfectly for sample inputs.

By writing int arr[ arraySize ]; you are creating an array of 10 elements (i.e., from 0 to 9), while in the for loops, you start from 0 and move until 10.

Live Demo

• quidproquo: Thanks, the issues were as you said. Also the function call had to be adjusted. The 3rd argument in the call should be "arraySize - 1" as opposed to "arraySize" as per what you said.