Java - making a binary search recursive_问答_开发者

So for a few weeks I've been trying back and forth to create the following code into a recursive method...

public static int binarySearch(Comparable[] objArray,Comparable item)
{       
    int lower=0;
    int upper=objArray.length -1;
    int i=-1;    // if -1 is returned the search failed;
    int compareResult;
    boolean found= false;
   开发者_如何学Go while ((lower<=upper)&& (!found))
       {
        i=(lower+upper)/2;
        compareResult=item.compareTo( objArray[i]);
        if (compareResult<0)
           {
            upper=i-1;
           }
         else
            if (compareResult>0)
               {
                lower=i+1;
               }
         else
            {
                found=true;    //item found in spot i
            }

       }// end of while
       if (found==false) return -1; else return i;

}

I know I must redefine the ints and use a couple ifs, but without a while loop I don't understand how to get to the final recursive code that I want. Any suggestions? Thanks

-D

The main problem that is stopping you from seeing the recursion is that your method's arguments are simply an array and a comparator. Were you to pass the starting and ending index (what one typically did in older language), you'd see the possibility of recursion.

I usually don't like to give out pseudo code for such questions, preferring instead to give you hints as of the structure and nature of the algorithm. However, there is no way you will be able to put the 2+2 together when your methods are defined in such a way. So I'm going to make an exception here:

Instead of this (which is what you have):

public static int binarySearch(Comparable[] objArray,Comparable item)
{       
    int lower=0;
    int upper=objArray.length -1;

You have this (this is java-like pseudocode, highly simplified and without error checking, you need to work the actual syntax details):

public static int binarySearch(Comparable[] objArray,Comparable item)
{       
    return bSearch(objArray, item, 0, objArray.length -1);
    ....

private static int bSearch(Comparable[] objArray,Comparable item, int lower, int upper)
{
   if( lower > upper /* not found */){ return -1; };

   int pivot = ((int)((upper - lower) / 2)) + lower;

   int cmp = objArray[pivot].compareTo(item);

   if( cmp == 0 ){ return pivot; }
   else if (cmp < 0 ){ return bSearch(objArray,item, lower, pivot - 1); }
   else{ return bSearch(objArray,item, pivot+1, upper); }
}

Again, you need to work the actual syntax and parameter validation, but other than that, this is the typical pseudo-code for a recursive binary search. You should have seen this and worked on it ad nausea at a sophomore programming course at the latest.

Recursion takes place in that:

If your array is sorted, and
If you start the comparison in the middle, aka the pivot,
And the comparison fails,
Then
You know you only need to search one half (either the upper half if target > pivot or the lower half if target < pivot).

So you take the half that you are going to search on, and execute the exact same steps on it again. What better way to do so than to call the exact same algorithm, the exact same function on just that part, that subset of your input?

That's recursion.

Edit: Elaborating in the previous example, when you want/need to implement something recursively in Java, it is better to have an utilitarian method that takes the data structure as a whole (say just the array and the comparison object as you did in your example).

Then have that call an internal method that does the actual recursion (and which has to deal with parameter passing.) The reason for this is that your callers do not have to pass the lower and upper indexes (since they can be computed out of the array object.)

In other, lower level languages like C, Pascal or Ada, you sometimes cannot compute such arguments and have to declare your recursive functions with parameters passed explicitly by your callers.

Ergo why I split the recursion in a separate bSearch function in the above pseudo-code.

Well, consider how you might recurse... after you've performed one comparison, you've narrowed down the search scope, right? So you need to indicate that in the arguments to the recursive method.

Try passing in the current known lower and upper bounds as arguments, instead of the while loopo - and change your while condition test to an initial test to see whether you've finished.

If you understood recursion already, skip this.

Recursivity works like this:

You have one ( or more ) base condition(s). These will be used to know when to stop.
You have input parameters. One ( or many ) of this input parameter will be used for the stop condition.
You have some operation to do, and this operation will be "solved" by invoking the same function with new parameters ( because using the same will recurse forever )

So, with this information in mind you could do something like this pseudo:

boolean contains( element ,  list)  { 
   //Q. what is the base condition? 
   //A. to know if there are elements in the list right?

   if list.isEmpty()?  return false; // not found in an empty list

   // Q. What other base condition we may try? 
   // A. If the list contains only one element, we may see 
   // if it is our element.
   if list.size() == 1 
        return list.firstElement() == element // true if they are false otherwise

   // Finally we may try as base condition to test 
   // if our element is in the middle of the list
   if list.middleElement() == element ?  return true // we found it


   // Ok, none of our base contidion worked.
   // Now we have to perform some operation 
   // Here's the recursion magic:
   // Solve your problem by invoking this same function ( re-course it ) 
   // with different arguments. In this sample, we 
   // split the original list in two.

    return  contains( element , list.firstHalf() )  
            or contains( element , list.secondHalf() )

   // you may read it as: 
   // "this list contains element if it is in the first half or it is in the second half 
}

By splitting the list in two, the search will narrow to a point where either the list contains one element or is empty. When that happens our base conditions will stop the recursion.

As you may see, it is lot easier if you first identify the base conditions, and then identify how to modify the parameters.

Is important to first try this in pseudo-code or with pencil and paper before attempting doing it in code. As you see in my example I invoked auxiliary methods ( firstElement(), middleElement(), firstHalf(), secondHalf() ) because they are not relevant to the problem. You have to first understand how to solve the problem and then pass to language specific problems.

I hope this help you to better understand recursion.

If you haven't try this link

Imagine this:

You are getting a smaller array to search in based on some condition. But your function's purpose is also to search for an element in the array. So, instead of working on it yourself, let a fresh call to the same function handle it. You just worry about the return value. If it is -1, you know the element was now found and you return -1 as well. If, anything else comes back, return that as well since it is the index of the found element.

You need to learn about a particular technique of recursion called "Divide and Conquer".

Basically, if you can divide the problem into two smaller identical problems, then you can easily apply recursion provided that eventually your divisions reduce the problem into something that is easily solved.

In this case, you are looking in an array to find an item. A Divide and conquer solution would then look like:

If I have a sorted array, I can compare the item I'm looking for to the middle element in that array. If it doesn't match, I select the smaller array in the direction (higher or lower) that corresponds to where I want to look and I'll repeat the process.
If I have an array of size one, then I only need to compare the item to the one I'm looking for, if it's not in there, then the element doesn't exist in that array.
If I have an array of size zero, then the element I'm looking for doesn't exist in that array.

Exit conditions should always be checked first. This prevents recursion where it isn't appropriate and guarantees that with each recursive evaluation you'll make sure that you stopped first if it was appropriate to stop.

boolean exists(Comparable[] X, Comparable item) {

   if (X.length == 0) return false;
   if (X.length == 1) return (X[0].compareTo(item) == 0);
   int pivot = X.length / 2; // integer math assures an integer result
   if (X[pivot].compareTo(item) == 0) return true;
   if (X[pivot].compareTo(item) < 0) {
     Compareable[] right = new Comparable[X.length-pivot-1];
     System.arrayCopy(X, pivot+1, right, 0, right.length);
     return exists(right, item);
   } else {
     Compareable[] left = new Comparable[X.length-pivot-1];
     System.arrayCopy(X, 0, left, 0, left.length);
     return exists(left, item);
   }

}

It's pseudo-code and not optimized, but it should get you thinking the way you need. Try out the technique on a few self-created problems; because, it is such an important concept that you don't want to base your understanding on just the homework problem (or two) assigned. You need to have a good understanding of this idea; it will be seen again in both school and work.