Seinfeld Seinfeld - 1 month ago 15
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));
}
}

Answer

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