Seinfeld - 1 year ago 78
Java Question

# How to grasp the concept of Binary Search recursion, with the example given in Java ?

Lately, I realized that I don't get the recursion as much as I thought so. That's why I'm trying to find as many examples as possible to figure it out, but I got caught very fast.

It's simple Binary Search code that works, yet I have very hard time understanding the recursion part. Especially because I don't see how anything changes with each further step. If at any point there was +1 or -1 given to any of variables, I might get it, but here variables are passed naturally, without any changes.

``````public class BinarySearchRecursion {
public static int binarySearch(int[] array, int value, int start, int end) {
if ((end - start) <= 1) {
if (array[start] == value)
return start;
if (array[end] == value)
return end;
return -1;
}

int midPoint = (start + end) / 2;
if (array[midPoint] > value) {
return binarySearch(array, value, 0, midPoint);
} else {
return binarySearch(array, value, midPoint, end);
}

}

public static void main(String[] args) {
int[] a = { 4, 9, 10 };
System.out.println(binarySearch(a, 10, 0, a.length - 1));
}
}
``````

You seem to be misled by thinking that the parameter called `start` is the same variable throughout the different recursive calls - but this is not the case (and similarly for `end`). There is no direct connection between the value of a particular parameter in different recursive calls, even though it's got the same name. Instead, the parameter values are passed by position: when you call `binarySearch`, whatever expression you write in the third parameter position will become the value of `start` in the new call.
So if `array[midPoint] > value` is true, you'll call `binarySearch(array, value, 0, midPoint)`, which is actually a bug - it's supposed to be `binarySearch(array, value, start, midPoint)`. This means that in the new call, the value of `start` will be the same as in this call, but the value of `end` will be the value that this call computed for `midPoint`. Otherwise, you'll call `binarySearch(array, value, midPoint, end)`, so that in the new call, the value of `start` will be `midPoint`, and the value of `end` will be the same as in this call.
(This goes for all methods, not just recursive ones. Also, note that `array` and `value` do keep their values throughout the recursive calls, but that's because you "pass them to themselves" in the first and second parameter position.)