CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Need Help with Binary Search Function

1. Junior Member
Join Date
Nov 2014
Posts
1

## 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.

2. ## 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

3. Elite Member Power Poster
Join Date
Aug 2000
Location
West Virginia
Posts
7,716

## 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.

4. Member +
Join Date
Jul 2013
Posts
576

## Re: Need Help with Binary Search Function

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)
Last edited by razzle; November 10th, 2014 at 02:03 AM.

5. ## 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)?

6. ## Re: Need Help with Binary Search Function

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.

7. ## 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

8. ## Re: Need Help with Binary Search Function

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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•