Need Help with Binary Search Function

[dearpaigejaclyn]

I was instructed to write a binary search function which would return true if an element, inputted by the user, was found in the array, and false if it was not. I'm not sure why, but my function always returns false. My code is as follows.

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

//binary search function
bool search (int array[], int item)
{
int high=99;
int low=0;
while(high>low and high!=low)
{
int mid=((low+high)/2);
if (item==array[mid])
{
return true;
}
else if (item<array[mid])
{
high=(mid-1);
}
else if (item>array[mid])
{
low=(mid+1);
}
}
return false;
}

//main to test function
int main()
{
const int n=100;
int a[n];
srand ( time(0) );
for (int g=0;g<n;g++)//inputting random #s into the array, as instructed
{
int p = rand() % 1001;
if (p<0)
{
p=p*-1;
}
a[g]=p;
}
//bubble sort to make the binary search run properly
for(int x=0; x<n; x++)

{

for(int y=0; y<n-1; y++)

{

if(a[y]>a[y+1])

{

int temp = a[y+1];

a[y+1] = a[y];

a[y] = temp;

}

}

}
for (int r=0; r<n; r++) //outputting the array so I know that the things I ask it to search for are/are not in the array
{
cout << a[r] << " ";
}
int item;
cout << "Enter an item to search for: ";
cin >> item;
if (search(a, item))
cout << "The number being searched for was found in the array." << endl;
else
cout << "The number being searched for was not found in the array." << endl;
return 0;
}

Any words of wisdom as to why my code does not fulfill it's purpose would be appreciated.

[2kaud]

When posting code, please use code tags so that the code shown is readable. Go Advanced, select the formatted code and click '#'.

while(high>low and high!=low)

Shouldn't this be

while(high>low && high!=low)

Note that rand() produces a number between 0 and RAND_MAX so will never be less than 0. See http://msdn.microsoft.com/en-us/library/398ax69y.aspx

[Philip Nicoletti]

while(high>low and high!=low)

is legal. There are a number of alternate tokens like this ("bitor" , "xor" , "or" , etc).

Personally, I would not use them as they are seldom seen in code.

[razzle]

Any words of wisdom

Yes, the devil's in the boundary cases.

I haven't checked too carefully but in this case I think you must allow the loop to be entered a final time when high equals low, like

while (high >= low)

[monarch_dodra]

Given your input data, you'vé got a 9 in 10 chance your function *should* return false. Are you sure it *always* returns false? Did you run it at least 30 times, or change your input data (say numbers from 0 to 20)?

[2kaud]

while(high>low and high!=low)

is legal. There are a number of alternate tokens like this ("bitor" , "xor" , "or" , etc).

Personally, I would not use them as they are seldom seen in code.

using and doesn't compile in my VS2013.

[2kaud]

while(high>low && high!=low)

if high is greater than low, then high is not equal to low and both parts of the and are true so the and condition is true.

If high equals low, then the first part of the and is false hence the whole and condition is false.
if high is less than low, then the first part of the and is false and hence the whole and condition is false.

You have effectively

while (high > low)

This doesn't take into account the scenario where high will equal low. See razzle's post #4

[monarch_dodra]

using and doesn't compile in my VS2013.

It *is* part of the c++ standard. In C, they are macros defined in iso646.h.

Apparently, in VS C++, you still have to include ciso646.

Fun fact: VS allows these keywords as identifiers, even though they are c++ restricted keywords.