Binary Search

[quantumbrath]

I am getting a logic error. It seems simple but its not working


#include <iostream>
using namespace std;

int main(){

int numarray[]={107, 110, 215, 305, 405, 505};
int maxNumElements = 6;
bool elementFound = false;
int inputValue;
int i = 0;
int lowElement = 0;
int highElement = maxNumElements;

cout << "Please enter a value" << endl;
cin >> inputValue;

while(elementFound != true && lowElement < highElement){

i = ((lowElement + highElement) / 2);



if ( inputValue == numarray[i] )
{
elementFound = true;


}

else

{
if (inputValue < numarray[i])
{
highElement = i - 1;
}


else
{
lowElement = i + 1;
}

}
}
if (elementFound == true)
cout << "Value found " << inputValue << " at index " << i;

else
cout << "value not found " << inputValue;


return 0;
}

[jonnin]

close! just use 'i' here, don't modify it that is causing it to skip and not see some values. I is modified all you need already.
{
if (inputValue < numarray[i])
{
highElement = i ;
}


else
{
lowElement = i;
}

[dhayden]

The trick with binary search is to be clear on exactly what highElement and lowElement mean. Specifically, is numArray[highElement] a possible match? What about numArray[lowElement]?

I'd arrange them such that numArray[lowElement] <= inputValue < numArray[highElement]. This conforms to the way the standard library works and it's a nice way to think about all intervals. Now let's look at your code with this in mind:

int lowElement = 0;   // okay
int highElement = maxNumElements;   // highElement is out of bounds but that's okay. 

...

if ( inputValue == numarray[i] ) {
    elementFound = true;
} else {
    if (inputValue < numarray[i]) {
        highElement = i - 1;  // wrong since numArray[i-1] might be inputValue
        // This should be highElement = i;
    } else {
        lowElement = i + 1;  // Okay. We know that numArray[i] != inputValue so may as well set lowElement to the next possible value
    }
}

One more note, check your code for the cases when inputValue is smaller than the smallest value in the array, or larger than the largest value.