recursive binary search

[pika]

i have here a simple recursive binary search. it seems to work well enough until i try to search for a value that does not exist. why doesn't it work?

would appreciate any help. thanks!

int bsearch_recur(int first, int last, int value, int data[])
//return the index that matches the value
{
	int middle = (first + last+1)/2;


	if(data[middle] == value)
	{
		return middle;
	}
	else
	{
		if(first >= last)
		{
			//error! doesnt exist?
			return -1;
		}
		else
		{
			if(value < data[middle])
			{
				bsearch_recur(first, middle, value, data);
			}
			else
			{
				bsearch_recur(middle, last, value, data);
			}
		}
	}
}

[nossrannug]

try this:
middle is first+last/2. and you need to increase by one or reduce by one somewhere else.

[jRaskell]

Because line 13 will never evaluate to true.

Let's take a trivial example. You have the dataset 1, 3. You search for value 2 in the dataset.
So your function call will pass in the following parameters for first, last, and value: 0, 1, 2.

middle = (first + last + 1) / 2;
middle = (0 + 1 + 1)/2;
middle = 1;

data[1] = 3, and first is not greater than or equal to last. You thus don't hit either of the recursion terminating return calls.
You value of 2 is less than data[1] of 3, so you call bsearch_recur again with the following parameters: 0, 1, 2.

But wait, that's the same as the first call. You've descended into an infinite recursive spiral that eventually overflows the stack and aborts the executable.

[imi]

middle is first+last/2. and you need to increase by one or reduce by one somewhere else.

First you need () around the addition and second better use "middle = first + (last-first)/2", because first+last can be already a nasty integer overflow for very large integers.

As with ALL common algorithms: Look at wikipedia. They got pseudo-code.

Ciao, Imi.

[pika]

i'm sorry...
i've been struggling to find a solution, but i just can't see how i can fix this.

can someone help?

[pika]

well...
i found a temporary solution, but it looks terribly awkward.

i have a couple of global variables:

int prevfirst, prevlast;

then i have this:

int bsearch_recur(int first, int last, int value, int data[])
//return the index that matches the value
{
	int middle = (first + last)/2;


	if(data[middle] == value)
	{
		return middle;
	}
	else
	if(data[last] == value)
	{
		return last;
	}
	else
	{

		{
		
			
			if(first == prevfirst && last == prevlast)
			{
				//error! doesnt exist?
				return -1;
			}
			else
			{
				if(value < data[middle])
				{
					prevfirst = first;
					prevlast = last;
					bsearch_recur(first, middle, value, data);
				}
				else
				{
					prevfirst = first;
					prevlast = last;
					bsearch_recur(middle, last, value, data);
				}
			}
		}
	}
}

i noticed that it couldnt detect the last element, so i did a quick fix. isnt there a more elegant way of going about this?

[justAbeginner]

if i understood u , u want to make a function that does the same thing as function search from libary algorithm?
if that is the case, than yes, there is a more elegant way...

[pika]

if there is, then what is it?

[justAbeginner]

first u send a pointer to the first element of the array, and another pointer that points after the last element, and the value the search needs to find, after that a simple
while loop should do the trick.

[jsmith]

I'm pretty sure OP is doing a recursive binary search because the assignment requires it.
Otherwise the whole thing could be done in 1 line of code with std::find().

[jRaskell]

Here's a hint for you. Your problem starts right at the beginning in how you're calculating your middle index.

Check out this page for detailed info on implementing a binary search algorithm: http://en.wikipedia.org/wiki/Binary_search_algorithm

In particular, look at how the flowchart describes how to generate your index position, and how it uses that index position to determine a "not found" condition.

On a separate subject, your two globals. With the above info you'll be able to eliminate them from your algorith, but for future reference, you could have preferably used two statics in the function call instead of globals.

[imi]

if there is, then what is it?

http://www.cplusplus.com/reference/stl/multimap/lower_bound/

Ciao, Imi