Results 1 to 4 of 4
  1. #1
    marsluo is offline Member
    Join Date
    Apr 2011
    Posts
    3
    Rep Power
    0

    Default Would anyone please help with this?

    The following code is a simple recursive binary search method that is supposed to return the index of the first match in an array, or -1 while no match. The test case result shows that no matter what if-then case it jumps to, it returns only 0, which I think, is from the very last statement. But, that statement can't be removed, otherwise "no return" error occurs. Would anyone help figure this out? Thanks:)



    public int findLocation(int[] anArray, int aTarget, int lowIndex, int highIndex){

    if(lowIndex>highIndex){
    System.out.println("can't find it!");

    return -1;
    }

    Mid=(int) (lowIndex+highIndex)/2;

    if(anArray[Mid]==aTarget){
    System.out.println("There is a match!");
    return Mid;

    }


    if(anArray[Mid]<aTarget){
    lowIndex=Mid+1;
    findLocation(anArray, aTarget, lowIndex, highIndex);
    }
    else if(anArray[Mid]>aTarget){
    highIndex=Mid-1;
    findLocation(anArray, aTarget, lowIndex, highIndex);
    }

    return 0;
    }

  2. #2
    doWhile is offline Moderator
    Join Date
    Jul 2010
    Location
    California
    Posts
    1,642
    Rep Power
    7

    Default

    readable code == code tags ;) In other words, it helps to flank your code with the code tags. The recursive calls do not make use of the returned value of those method calls. There shouldn't be a need to return 0 at the end of the method, as the calls above should return -1, the current value, or the result of the findLocation method.

  3. #3
    marsluo is offline Member
    Join Date
    Apr 2011
    Posts
    3
    Rep Power
    0

    Default Re:

    Sorry for the unfinished code pasting. The following is a better version. The logic of code is not important, because I've tested all the if-then cases, and get all the verifying 'system.out.print....' statement working. But, all the following return statements seems totally overwhelmed by the very last statement "return 0". As you mentioned, I also think this statement is dummy. But, I can't miss the statement, since the Eclipse report 'no return' error on it. Thanks



    public int findLocation(int[] anArray, int aTarget, int lowIndex, int highIndex){
    //Pre: anArray is in non-decreasing order, fulfilled by the method "addInitialValue";
    //Post:
    /*anArray[x] = aTarget for some index x AND returnInt is the smallest such x
    –OR –
    There is no x with anArray[x] = aTarget AND returnInt = -1
    */
    //SG1: determine the midpoint of a sub-region of an array or the whole array itself
    //SG2: Locate the region potentially containing the target
    // a) Left(lowIndex,Mid): update the highIndex of the left sub-region and apply recursively on this region -OR-
    // b) Right(Mid, highIndex): update the lowIndex of the right sub-region and apply recursively on this region -OR-
    // c) Mid: target found, return the value of Mid
    //SG3: the Target can not be found, return -1


    if(lowIndex>highIndex){//SG3 fulfilled
    System.out.println("can't find it!");
    return -1;
    }

    Mid=(int) (lowIndex+highIndex)/2;//SG1 fulfilled

    if(anArray[Mid]==aTarget){//SG2 c) fulfilled
    System.out.println("There is a match!");
    return Mid;

    }

    if(anArray[Mid]<aTarget){//SG2 b) fulfilled
    lowIndex=Mid+1;
    findLocation(anArray, aTarget, lowIndex, highIndex);
    }
    else if(anArray[Mid]>aTarget){//SG2 a) fulfilled
    highIndex=Mid-1;
    findLocation(anArray, aTarget, lowIndex, highIndex);
    }

    return 0;
    }
    Last edited by marsluo; 04-18-2011 at 04:19 AM.

  4. #4
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,789
    Rep Power
    7

    Default

    Quote Originally Posted by marsluo View Post
    But, all the following return statements
    What return statements?
    Java Code:
    findLocation(anArray, aTarget, lowIndex, highIndex);
    // snip
    return 0;
    See how the value that is returned from the recursive call is thrown away. You exit the if statement and always return 0.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •