Results 1 to 4 of 4

- 04-18-2011, 01:37 AM #1Member
- Join Date
- Apr 2011
- Posts
- 3

- Rep Power
- 0

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

}

- 04-18-2011, 02:44 AM #2Moderator
- Join Date
- Jul 2010
- Location
- California
- Posts
- 1,638

- Rep Power
- 13

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.

- 04-18-2011, 03:19 AM #3Member
- Join Date
- Apr 2011
- Posts
- 3

- Rep Power
- 0

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

- 04-18-2011, 04:00 AM #4

## Bookmarks