Recursion counter

Thread view:

timorrill - 08 Nov 2007 20:02 GMT

I am working on a Recursive binary search algorithm (which probably
still needs some tweaking), but I am interested in counting the levels
of recursion encountered while searching for a particular element in a
sorted array.

Here's what I have for the method:

static int binsearch(int key, int[] x, int i, int j)
{
int mid;
if (i > j)
return i;
mid = (i+j)/2;
if (key <= x[mid])
return binsearch(key, x, i, mid-1);
else if (key > x[mid])
return binsearch(key, x, mid+1, j);
else
return mid;
}

What is the best way to introduce this counter?

Reply to this Message

Are Nybakk - 08 Nov 2007 20:43 GMT

> I am working on a Recursive binary search algorithm (which probably
> still needs some tweaking), but I am interested in counting the levels
[quoted text clipped - 18 lines]
>
> What is the best way to introduce this counter?

Have an int value outside the method that you increment in the base case
("if(i > j) {....}").

Reply to this Message

Are Nybakk - 09 Nov 2007 14:04 GMT

>> I am working on a Recursive binary search algorithm (which probably
>> still needs some tweaking), but I am interested in counting the levels
[quoted text clipped - 21 lines]
> Have an int value outside the method that you increment in the base case
> ("if(i > j) {....}").

Err... I'm not sure what I was thinking. The base case is of course the
last call to the method and the last only.

Reply to this Message

Daniel Pitts - 08 Nov 2007 21:01 GMT

Sorry if this is a double post, network trouble again...

> I am working on a Recursive binary search algorithm (which probably
> still needs some tweaking), but I am interested in counting the levels
> of recursion encountered while searching for a particular element in a
> sorted array.
>
> Here's what I have for the method:

[snip code]

> What is the best way to introduce this counter?

Why not use Arrays.binarySearch()?

As for counting, you'd be best off passing in a reference to a holder
object that holds the count. This doesn't sound like a useful feature
though, and will likely add a lot of unnecessary overhead.

Also, binary search can be done iteratively. In languages like Java,
the iterative approach tends to be better. So, in other words, I
suggest strongly that you use Arrays.binarySearch, unless you are doing
this as an exercise, rather than for any production code.

Signature

Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>

Reply to this Message

Piotr Kobzda - 08 Nov 2007 21:30 GMT

[...]

> What is the best way to introduce this counter?

Assuming you _really_ need that, one simple approach might be:

static int binsearch(int key, int[] x, int i, int j) {
return binsearch(key, x, i, j, 0);
}

private static int binsearch(int key, int[] x, int i, int j, int
depth) {
int mid;
if (i > j)
return i;
mid = (i+j)/2;
if (key <= x[mid])
return binsearch(key, x, i, mid-1, depth+1);
else if (key > x[mid])
return binsearch(key, x, mid+1, j, depth+1);
else
return mid;
}

piotr

Reply to this Message

Stefan Ram - 08 Nov 2007 23:03 GMT

>mid = (i+j)/2;

»Specifically, it fails if the sum of low and high is
greater than the maximum positive int value (2^31 - 1). The
sum overflows to a negative value, and the value stays
negative when divided by two.«

http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

But in <fecs7p$faf$1@inews.gazeta.pl> you already suggested:

result = ((this.number0 ^ this.number1) >> 1) + (this.number0 & this.number1);

In reply to my code in

http://www.purl.org/stefan_ram/java/de/dclj/ram/type/pair/PairOfIntAndInt.java

(I still have not answered your question »What about using
possibly a bit faster approach here: result = ((this.number0 ^
this.number1) >> 1) + (this.number0 & this.number1); ?« in
<fecs7p$faf$1@inews.gazeta.pl>. I have entered the task to
answer this in my todo-list, because I was not able to answer
immediatly. I hope that some day, I will answer. Sorry for the delay!)

Reply to this Message

Daniel Pitts - 09 Nov 2007 00:06 GMT

>> mid = (i+j)/2;
>
> »Specifically, it fails if the sum of low and high is
> greater than the maximum positive int value (2^31 - 1). The
> sum overflows to a negative value, and the value stays
> negative when divided by two.«

another algorithm to find the average:
mid = low +(high-low)/2;

Although, in order for low+high to be > (2^31-1), you would need
high>(2^30), which implies an array of at least 2^30+1 elements long.
which is 1,073,741,825 elements long.

While not impossible, generally you'll end up with some other things to
worry about by that point.

Signature

Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>

Reply to this Message

Piotr Kobzda - 09 Nov 2007 00:44 GMT

>> mid = (i+j)/2;
>
[quoted text clipped - 4 lines]
>
> http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

I seen that mistake (should add a note about that...).

> But in <fecs7p$faf$1@inews.gazeta.pl> you already suggested:
>
> result = ((this.number0 ^ this.number1) >> 1) + (this.number0 & this.number1);

Yes, that should work. However, negative values are not used in the
OP's case (array indices), so the JB proposed approach:

mid = (i+j)>>>1;

is enough, and most likely faster than mine here.

> In reply to my code in
>
[quoted text clipped - 6 lines]
> answer this in my todo-list, because I was not able to answer
> immediatly. I hope that some day, I will answer. Sorry for the delay!)

No problem Stefan. Hope you'll find it useful some day...

piotr

Reply to this Message

Eric Sosman - 08 Nov 2007 22:05 GMT

timorrill wrote On 11/08/07 15:02,:

> I am working on a Recursive binary search algorithm (which probably
> still needs some tweaking), but I am interested in counting the levels
[quoted text clipped - 16 lines]
> return mid;
> }

Side-issue: Notice that the final `return' can
never be executed.

Signature

Eric.Sosman@sun.com

Reply to this Message

Mark Rafn - 08 Nov 2007 22:08 GMT

>I am working on a Recursive binary search algorithm (which probably
>still needs some tweaking), but I am interested in counting the levels
>of recursion encountered while searching for a particular element in a
>sorted array.

For a learning excercise, this is fine. For production code,
Arrays.binarySearch() is likely to be faster, clearer, and better-debugged.

For this algorithm, even doing it yourself iteratively is likely to be faster
and easier to follow. And instead of "depth" you just track "iteration
number". Think something along the lines of
while ((lowIndex < highIndex) && (haystack[lowIndex] != needle)))

>Here's what I have for the method:
>
[quoted text clipped - 11 lines]
> return mid;
> }

Generally, you'd make this private, and have a public version that's just
(slightly altered to fit conventions about naming and param order)

public static int binSearch(int[] haystack, int needle) {
binSearch(haystack, needle, 0, haystack.length-1);
}

>What is the best way to introduce this counter?

The obvious way is to pass another argument.

private binSearch(
int[] haystack, int needle, int lowIndex, int highIndex, int depth) {
...
return binSearch(haystack, needle, newLow, newHigh, depth + 1);
...
}

Other ways include looking at the VM callstack via
Thread.currentThread.getStackTrace(), but this is a bunch of code and it's
probably more work for the VM than the algorithm itself.
--
Mark Rafn dagon@dagon.net <http://www.dagon.net/>

Reply to this Message

Roedy Green - 09 Nov 2007 00:03 GMT

On Thu, 08 Nov 2007 12:02:19 -0800, timorrill
<timothy.morrill@gmail.com> wrote, quoted or indirectly quoted someone
who said :

>What is the best way to introduce this counter?

you could used a static or instance variable. If you wanted to do it
purely with local variables, you must pass the current value of the
counter and return the incremented one.

Signature

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

Reply to this Message

Recursion counter

Free Magazines