Results 1 to 4 of 4
- 04-18-2011, 02:37 AM #1
Member
- 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, 03:44 AM #2
Moderator
- Join Date
- Jul 2010
- Location
- California
- Posts
- 1,638
- Rep Power
- 12
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, 04:19 AM #3
Member
- 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 05:19 AM.
- 04-18-2011, 05:00 AM #4
Bookmarks