Binary Search Help Repost.

Didn't the compiler give you a warning message something about [font=verdana, arial, helvetica, sans-serif][color=#000000]

BinSearch[/font]

not returning a value? Because it's only returning a value, when it's found the element. Hmm.

What does it return when it finds the element? In what range? Hmm. It returns a zero or positive value.

Hmm. That means negative values aren't used. Hmm.

That means we could use negative values for other purposes, such as indication that the element is not used? Yay! Let's use -1 for indicating that no element is found (that's pretty standard).
We could even use more negative numbers for other error codes, such as the input numElements was negative... That's another story.

But how can we decide if the element is not found? Wait. We already see that the [font=verdana, arial, helvetica, sans-serif][color=#000000]

BinSearch[/font]

is only returning a value when it's found something. If it doesn't return, then what happens? Hmmm.
We get to the end of the for loop!

So we know we have to return -1 when nothing is found, and we know that we arrive after the for loop when nothing is found.

Let's put a return -1 after the for loop then!

Yay! We have signalled that we haven't found the element, and we can act upon it by checking the return value of [font=verdana, arial, helvetica, sans-serif][color=#000000]

BinSearch[/font]

in Main.
Hmm, that also means we successfully decoupled the logic from the input/output.

In this particular program, we can print stuff differently depending on the return value. If it's -1, we print "nothing found". If it's >= 0, we print the value.

Damn! What was that?? Lol. I've reposted it

@szecs Hey, thanks for your replyl!

Do you mean this:


#include<iostream>
using namespace std;

int BinSearch(int data[], int numElements, int searchKey); // Prototype

int main()
{
int data[] = {1, 4, 5, 6, 9, 14, 21, 23, 28, 31, 35, 42, 46, 50, 53, 57, 62, 63, 65, 74, 79, 89, 95};
int numElements = 23; // Size of the Array is 23!!!
int searchKey;
int found;

for(int i = 0; i < numElements; i++)
cout << data << ", ";
cout << endl;

for(;;)
{
cout << "Enter search key: (-1 to exit) "; // I want to quit when I press 'x'. Please let me know.
cin >> searchKey;

if(searchKey == -1)
{
cout << "Exiting\n";
break;
}

found = BinSearch(data, numElements,searchKey);

if(found == -1)
cout << searchKey << " not found\n";

cout << searchKey << " is in position " << found << endl;
}

}

int BinSearch(int data[], int numElements, int searchKey)
{
int mid;
int beg = 0;
int end = numElements;
bool not_found = 1;

// Algorithm Begins.
for(int i = beg; i <= end;)
{
mid = (beg+end)/2;

if(data[mid] == searchKey)
return mid;

else if(data[mid] > searchKey)
end = mid - 1;

else if(data[mid] < searchKey)
beg = mid + 1;

else
return -1;
}


}


This doesn't seem to work. Sorry, I didn't completely understand what you meant...

And Yea, the compiler's telling me this:
warning C4715: 'BinSearch' : not all control paths return a value

No. I didn't mean that. Just think over what I said in my first post.
"End of for loop" may be misworded. I meant "after the for loop".

The complier says not all control paths return a value. Can you figure out what path doesn't return in your code?
With your modifications the code still produces this warning message so that means you didn1t insert the return -1 where I implied.

And think about it: what control path doesn't return value? The path that doesn't find the value. Just debug it on paper. That is the exact point where you have to insert the return -1.


Maybe my English sucks, but I think this should be clear.

And please pay attention to warning messages.

Thanks! No more warnings now. I'm returning -1 outside the for loop in the BinSearch function
But how do I print a message like "Element not found" using that return value -1 ??

Your English doesn't suck, I'm pure rookie

Some spoonfeeding:

found = BinSearch(data, numElements,searchKey);

if( found == -1 )
{
cout << Element not found << endl;
}
else // if( found >= 0 ) // for other error codes
{
cout << searchKey << " is in position " << found << endl;
}

Some spoonfeeding:

found = BinSearch(data, numElements,searchKey);

if( found == -1 )
{
cout << Element not found << endl;
}
else // if( found >= 0 ) // for other error codes
{
cout << searchKey << " is in position " << found << endl;
}

Thanks for replying. Did You mean this:



#include<iostream>
using namespace std;

int BinSearch(int data[], int numElements, int searchKey); // Prototype

int main()
{
int data[] = {1, 4, 5, 6, 9, 14, 21, 23, 28, 31, 35, 42, 46, 50, 53, 57, 62, 63, 65, 74, 79, 89, 95};
int numElements = 23; // Size of the Array is 23!!!
int searchKey;
int found;

for(int i = 0; i < numElements; i++)
cout << data << ", ";
cout << endl;

for(;;)
{
cout << "Enter search key: (-1 to exit) "; // I want to quit when I press 'x'. Please let me know.
cin >> searchKey;

if(searchKey == -1)
{
cout << "Exiting\n";
break;
}

found = BinSearch(data, numElements,searchKey);

if(found == -1)
cout << "Not Found!\n";

else cout << searchKey << " is in position " << found << endl;
}

}

int BinSearch(int data[], int numElements, int searchKey)
{
int mid;
int beg = 0;
int end = numElements;

// Algorithm Begins.
for(int i = beg; i <= end;)
{
mid = (beg+end)/2;

if(data[mid] == searchKey)
return mid;

else if(data[mid] > searchKey)
end = mid - 1;

else if(data[mid] < searchKey)
beg = mid + 1;
}
return -1;
}


Not working.

@szecs Hey, thanks for your replyl!

Do you mean this:


#include<iostream>
using namespace std;

int BinSearch(int data[], int numElements, int searchKey); // Prototype

int main()
{
int data[] = {1, 4, 5, 6, 9, 14, 21, 23, 28, 31, 35, 42, 46, 50, 53, 57, 62, 63, 65, 74, 79, 89, 95};
int numElements = 23; // Size of the Array is 23!!!
int searchKey;
int found;

for(int i = 0; i < numElements; i++)
cout << data << ", ";
cout << endl;

for(;;)
{
cout << "Enter search key: (-1 to exit) "; // I want to quit when I press 'x'. Please let me know.
cin >> searchKey;

if(searchKey == -1)
{
cout << "Exiting\n";
break;
}

found = BinSearch(data, numElements,searchKey);

if(found == -1)
cout << searchKey << " not found\n";

else cout << searchKey << " is in position " << found << endl;
}

}

int BinSearch(int data[], int numElements, int searchKey)
{
int mid;
int beg = 0;
int end = numElements;
bool not_found = 1;

// Algorithm Begins.
for(int i = beg; i <= end;)
{
mid = (beg+end)/2;

if(data[mid] == searchKey)
return mid;

else if(data[mid] > searchKey)
end = mid - 1;

else if(data[mid] < searchKey)
beg = mid + 1;
}

return -1;

}


This doesn't seem to work. Sorry, I didn't completely understand what you meant...

And Yea, the compiler's telling me this:
warning C4715: 'BinSearch' : not all control paths return a value

What doesn't work?
Doesn't print stuff? Doesn't print the right value? Never prints "not found"?

What are we debugging here actually??

I wan't to print "Not found" if a value which isn't found in the array is entered by the user.

I wan't to print "Not found" if a value which isn't found in the array is entered by the user.

I understand what you want, but in order to debug, we need to know what happens.
What happens instead?

Does it even print "whatever key is in position -1"?

Does the program work as expected when the key is found?

I don't know what we are debugging here.
Input? I'm not even sure you can input a single key like that. Doesn't cin input a string?
The algorithm? It should be fine
The output? Does it print anything at all?

Please, don't make us to setup a project and recomplie/debug the thing for you.

One problem is that your loop:
for(int i = beg; i <= end;)
{
mid = (beg+end)/2;

if(data[mid] == searchKey)
return mid;

else if(data[mid] > searchKey)
end = mid - 1;

else if(data[mid] < searchKey)
beg = mid + 1;
}

doesn't exit if the search target is not in the array. You should probably replace for(int i=beg;i<=end;) with while(beg<end), especially since the i variable is not doing anything.

I replaced for with while that helped. Thank You. @ szecs you're not the only one who didn't notice it . In another forum also, someone has just now figured it. THank you'll

--Sid

O wow, I didn't see there's no i++ in the for loop.
So indeed, you have an infinite loop.


It would have been much easier if you explained what happened in the very first place. I didn't know we have to debug the whole thing.


Please, learn to ask questions and learn to describe the problems in detail.

O wow, I didn't see there's no i++ in the for loop.
So indeed, you have an infinite loop.


It would have been much easier if you explained what happened in the very first place. I didn't know we have to debug the whole thing.


Please, learn to ask questions and learn to describe the problems in detail.

Sorry... Actually I didn't know there was a problem there.

Assuming that array is sorted that way, I believe one solution to the endless loop can be:
...
if(found != NULL)
cout << searchKey << " is in position " << found << endl;
else
cout << "Element not found.\n";
}
....
....
for(int i = beg; i <= end;)
{
mid = (beg+end)/2;

if(data[mid] == searchKey)
{
return mid;
}
else if(data[mid] > searchKey)
{
if(searchKey > data[mid-1]) //if searchKey is greater than the immediate previous element then searchKey not exists in array
return NULL;
end = mid - 1;
}
else if(data[mid] < searchKey)
{
if(searchKey < data[mid+1]) //similar to above comment
return NULL;
beg = mid + 1;
}
}

stuff...

As you are probably aware, indexing in C++ starts with zero. And NULL is zero too, so your code is not working as intended.

Plus your code is a lot more messy (with no gain at all) than the original code with the while, and it only breaks the loop with sorted lists.

@szecs
you're right about NULL, i could use a number like -999 as a flag. But what do you mean by saying break the loop with sorted lists and the original code with while, i think there isn't while loop in original code. I just tried to avoid endless loop in a simple way. Maybe I'm missing something...

What RulerOfNothing said. Use the while(beg instead of the buggy for, but with the same contents like in the first post.