Recursion counter

[timorrill]

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?

 

[Are Nybakk]

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?

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

 

[Daniel Pitts]

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.

 

[Piotr Kobzda]

timorrill wrote:

[...]

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

 

[Eric Sosman]

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

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

 

[Mark Rafn]

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:

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

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.

 

[Stefan Ram]

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 <[email protected]> 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
<[email protected]>. 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!)

 

[Roedy Green]

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.

 

[Daniel Pitts]

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

 

[Piotr Kobzda]

»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

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

But in <[email protected]> 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

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
<[email protected]>. 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!)

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


piotr

 

[Are Nybakk]

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?

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.