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,641
    Rep Power
    9

    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,807
    Rep Power
    10

    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
  •