Binary Search C++

[hous3aholik]

Hi! Im finishing up a lottery number generator and the only part im kinda lost in is the binary search part.
I have two strings = input[], random; I have to go through each subscript and check if it matches my already random generated number.

Thanks in advance to those who are willing to help.

[Labdabeta]

This is not too hard as far as I can tell. Your post is a little vague, but I think that you should just store the random number in a variable and check it against all the elements of your array.

[hous3aholik]

int binarySearch(char array[],int numElems,int value) //function heading
{
	int first = 0;				    // First element of list
	int last = numElems - 1;	    // last element of the list
	int middle;					    // variable containing the current 
	int position = -1;              // middle value of the list
	bool found = false;
	
	while (!found && first <= last)
	{
		middle = (last + first) / 2; 
		   
	if (array[middle] == value)
		{
           found = true;
           position = middle;
        }
                                     
	else if (array[middle] > value)
		last = middle - 1;		   // toss out the second remaining half of
								   // the array and search the first 
	else
		first = middle + 1;		   // toss out the first remaining half of
								   // the array and search the second
	}
	
	return position;

This is the binary search algorithm that im trying to use in my program. but it always returns true, even when its not.

[VernonDozier]

Line 27 - Shouldn't you be checking "found" to help decide what you need to return? What should you return if "found" is false? Is that what you are indeed returning?

[hous3aholik]

Line 27 - Shouldn't you be checking "found" to help decide what you need to return? What should you return if "found" is false? Is that what you are indeed returning?

Sorry vernon im not too clear on what you are trying to say. Do i have to do something different than that to compare my two strings?

[VernonDozier]

Not sure how I can phrase it differently. What's the function supposed to return when the number isn't found? Right now you return "position". You'd better check and make sure "position" is equal to what you want it to be equal to when the number isn't found. Display it to make sure. If it's not what you want it to be, you need to change it so that it is. if the "found" variable helps you do that, use it.

[hous3aholik]

okay i got it, hahaha it was so simple yet so confusing. The only thing now that im not too clear is how am i going to compare two strings for equality??

[VernonDozier]

>> okay i got it, hahaha it was so simple yet so confusing. The only thing now that im not too clear is how am i going to compare two strings for equality??

Strings? There are no strings here. This is supposed to be a binary search function. It's supposed to search an integer array for an integer and return the array index if found and return -1 if not found. No one but me knows what you're talking about. I only do because I'm familiar with your last thread.

And why is this still char[] instead of int[]?

int binarySearch(char array[],int numElems,int value)

[hous3aholik]

>> okay i got it, hahaha it was so simple yet so confusing. The only thing now that im not too clear is how am i going to compare two strings for equality??

Strings? There are no strings here. This is supposed to be a binary search function. It's supposed to search an integer array for an integer and return the array index if found and return -1 if not found. No one but me knows what you're talking about. I only do because I'm familiar with your last thread.

And why is this still char[] instead of int[]?

int binarySearch(char array[],int numElems,int value)

ooh so ill have to convert those strings back to int? the reason is because i copied and pasted it from my original code just as a reference. im in my mac, since my stupid pc's wireless card stopped working.

[VernonDozier]

>> the reason is because i copied and pasted it from my original code

Your original code should be long gone. Nobody cares about anything but your up-to-date code. You shouldn't either.

>> so ill have to convert those strings back to int?

What you'll have to do is stick some comments on the top of every single function so you and everyone else is clear about exactly what each function does, what parameters the function takes, and what the function returns. If you do that, these mistakes will go way down. This is a very detail-oriented, time consuming process. You need to take several steps back and think about the whole thing and be as explicit as possible.

[hous3aholik]

>> the reason is because i copied and pasted it from my original code

Your original code should be long gone. Nobody cares about anything but your up-to-date code. You shouldn't either.

>> so ill have to convert those strings back to int?

What you'll have to do is stick some comments on the top of every single function so you and everyone else is clear about exactly what each function does, what parameters the function takes, and what the function returns. If you do that, these mistakes will go way down. This is a very detail-oriented, time consuming process. You need to take several steps back and think about the whole thing and be as explicit as possible.

But does anybody know how could i compare those two strings in a binary search? i need to do it for each line of my file. and then compare it to the random generated numbers. The only way to do that is playing with the subscripts but how.

[VernonDozier]

>> But does anybody know how could i compare those two strings in a binary search?

Last post on this. I simply can't spend any more time on it. Straight from Wikipedia...

In computer science, a binary search or half-interval search algorithm locates the position of an item in a sorted array.

How do you compare two strings in a binary search? You don't. You don't compare TWO of anything in a binary search. You search an ordered array for some value. If you want to compare TWO things, you compare them with the == sign. There's no search, binary or otherwise. It's like asking "How do I tighten lug nuts with a hammer?" You don't. You pick the appropriate tool for the job.

>> i need to do it for each line of my file. and then compare it to the random generated numbers. The only way to do that is playing with the subscripts but how.

I'll reiterate. No one but me knows what you're talking about and I can't spend any more time on it. There are no strings in this thread, there's no random number generation in it, there's no file in it. Nobody but me knows about your prior thread, so if you need help on how to do something, you have to post everything that's relevant to your question in your thread.