Binary Search Help Repost.
Author
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.
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.
Author
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
. 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.
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.
Author
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;
}
}
...
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...
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<end) instead of the buggy for, but with the same contents like in the first post.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
