# Need Help with Binary Search Function

• November 9th, 2014, 01:47 PM
dearpaigejaclyn
Need Help with Binary Search Function
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.
• November 9th, 2014, 02:50 PM
2kaud
Re: Need Help with Binary Search Function
When posting code, please use code tags so that the code shown is readable. Go Advanced, select the formatted code and click '#'.

Code:

`while(high>low and high!=low)`
Shouldn't this be
Code:

`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
• November 9th, 2014, 05:00 PM
Philip Nicoletti
Re: Need Help with Binary Search Function
Code:

`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.
• November 10th, 2014, 01:59 AM
razzle
Re: Need Help with Binary Search Function
Quote:

Originally Posted by dearpaigejaclyn
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)
• November 10th, 2014, 03:34 AM
monarch_dodra
Re: Need Help with Binary Search Function
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)?
• November 10th, 2014, 03:40 AM
2kaud
Re: Need Help with Binary Search Function
Quote:

Originally Posted by Philip Nicoletti
Code:

`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. :(
• November 10th, 2014, 03:54 AM
2kaud
Re: Need Help with Binary Search Function
Code:

`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
Code:

`while (high > low)`
This doesn't take into account the scenario where high will equal low. See razzle's post #4
• November 10th, 2014, 05:48 AM
monarch_dodra
Re: Need Help with Binary Search Function
Quote:

Originally Posted by 2kaud
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.