Jump to content

  • Log In with Google      Sign In   
  • Create Account


Binary Search Help Repost.


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
22 replies to this topic

#1 Sid_TheBeginner   Members   -  Reputation: 157

Like
0Likes
Like

Posted 28 June 2012 - 11:40 PM

I've got the logic right and the algo seems to work fine. Now, that's epic for me Posted Image But..

I want to add 2 more features to this code:

1) Exit on pressing 'x'. For now I'm using -1 to exit.
2) Print a message "Element not found" when an element not present in the array is searched for. Yeah, I'm not able to figure that out :|
Well, Here goes my code:

[/size][/color][/font]

#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[i] << ", ";
	 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);

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

}

int BinSearch(int data[], int numElements, int searchKey) 
{
	 int position, 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;
		  }
      }

}

[font=verdana, arial, helvetica, sans-serif][color=#000000][size=3]

Thanks,
--Sid

Edited by Sid_TheBeginner, 28 June 2012 - 11:51 PM.


Sponsor:

#2 szecs   Members   -  Reputation: 2082

Like
1Likes
Like

Posted 28 June 2012 - 11:45 PM

Didn't the compiler give you a warning message something about BinSearch 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 BinSearch 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 BinSearch 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.

Edited by szecs, 29 June 2012 - 12:37 AM.


#3 Sid_TheBeginner   Members   -  Reputation: 157

Like
0Likes
Like

Posted 28 June 2012 - 11:52 PM

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

#4 Sid_TheBeginner   Members   -  Reputation: 157

Like
0Likes
Like

Posted 29 June 2012 - 12:29 AM

@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[i] << ", ";
	 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

Edited by Sid_TheBeginner, 29 June 2012 - 12:31 AM.


#5 szecs   Members   -  Reputation: 2082

Like
1Likes
Like

Posted 29 June 2012 - 12:36 AM

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.

Edited by szecs, 29 June 2012 - 12:39 AM.


#6 Sid_TheBeginner   Members   -  Reputation: 157

Like
0Likes
Like

Posted 29 June 2012 - 12:47 AM

Thanks! No more warnings now. I'm returning -1 outside the for loop in the BinSearch function Posted Image
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 Posted Image

#7 szecs   Members   -  Reputation: 2082

Like
0Likes
Like

Posted 29 June 2012 - 12:56 AM

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;
}

Edited by szecs, 29 June 2012 - 12:57 AM.


#8 Sid_TheBeginner   Members   -  Reputation: 157

Like
0Likes
Like

Posted 29 June 2012 - 01:05 AM

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[i] << ", ";
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. Posted Image

Edited by Sid_TheBeginner, 29 June 2012 - 01:11 AM.


#9 Sid_TheBeginner   Members   -  Reputation: 157

Like
0Likes
Like

Posted 29 June 2012 - 01:05 AM

@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[i] << ", ";
	 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


Edited by Sid_TheBeginner, 29 June 2012 - 01:06 AM.


#10 szecs   Members   -  Reputation: 2082

Like
0Likes
Like

Posted 29 June 2012 - 01:35 AM

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

What are we debugging here actually??

#11 Sid_TheBeginner   Members   -  Reputation: 157

Like
0Likes
Like

Posted 29 June 2012 - 01:43 AM

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

#12 szecs   Members   -  Reputation: 2082

Like
0Likes
Like

Posted 29 June 2012 - 01:55 AM

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.

#13 RulerOfNothing   Members   -  Reputation: 1142

Like
1Likes
Like

Posted 29 June 2012 - 02:03 AM

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.

#14 Sid_TheBeginner   Members   -  Reputation: 157

Like
0Likes
Like

Posted 29 June 2012 - 02:15 AM

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

--Sid

#15 szecs   Members   -  Reputation: 2082

Like
0Likes
Like

Posted 29 June 2012 - 02:18 AM

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.

Edited by szecs, 29 June 2012 - 02:19 AM.


#16 Sid_TheBeginner   Members   -  Reputation: 157

Like
0Likes
Like

Posted 29 June 2012 - 02:52 AM

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. Posted Image

#17 oobee   Members   -  Reputation: 101

Like
0Likes
Like

Posted 29 June 2012 - 03:16 AM

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;
}
}

#18 szecs   Members   -  Reputation: 2082

Like
0Likes
Like

Posted 29 June 2012 - 03:26 AM

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.

#19 oobee   Members   -  Reputation: 101

Like
0Likes
Like

Posted 29 June 2012 - 03:51 AM

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

#20 szecs   Members   -  Reputation: 2082

Like
0Likes
Like

Posted 29 June 2012 - 03:56 AM

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




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS