1

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

Improve this question
3
  • 4
    "without a while loop I don't understand how to get to the final recursive code"... you do it by making recursive calls. Didn't you get an explanation of recursion in class? Commented Dec 8, 2010 at 20:32
  • 1
    absolutely, however its certainly not my strong point and ive been stuck with this for quite awhile haha Commented Dec 8, 2010 at 20:34
  • 1
    Hey, at least you are trying :) Have you had a sophomore 200x-level programming course already? This should be standard bread-n-butter before completing all 200-x level programming courses before getting into the 300-x level ones. BTW, we worked on recursion (a lot) on my Pascal I course (the second one I took after BASIC) 18 years ago. Not trying to give you a lecture, but I hope you understand how critical it is to get this recursive sh*t down cold like the back of your hand ;) Commented Dec 8, 2010 at 20:55

5 Answers 5

Reset to default
5

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:

  1. If your array is sorted, and

  2. If you start the comparison in the middle, aka the pivot,

  3. And the comparison fails,

  4. Then

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

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

3

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.

Improve this answer

Comments

2

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

Improve this answer

Comments

1

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.

Improve this answer

Comments

1

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:

  1. 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.
  2. 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.
  3. 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.

Improve this answer

1 Comment

Just an observation: You are creating a brand new array and copy the contents of each half with each recursive call. This is basically creating O(log N) object instances and performing an equal amount of element copies (none of which is needed if we simply pass start and end index arguments down the recursive calls as one would typically do in traditional pseudocode specs of bsearch.)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.