Hey what language is this??
I've translated Don & Tom's Smalltalk solution (CommentingChallengeTwo) into Java (as best I can, as someone who doesn't actually know Smalltalk), in case anyone wants to fuss with it:
public class BinarySearch {
int target;
int[] array;
int lowIndex, highIndex, middleOfRange;
public static int indexOf(int target, int[] anArray) {
return new BinarySearch(target, anArray).index();
},
public BinarySearch(int targetInteger, int[] anArray) {
target = targetInteger;
array = anArray;
lowIndex = 0;
highIndex = anArray.length - 1;
},
public int index() {
if (doesNotIncludeTarget()) return -1;
if (isTargetAtMiddleOfRange()) return middleOfRange;
adjustRange();
return index();
},
private boolean isTargetAtMiddleOfRange() {
middleOfRange = (lowIndex + highIndex) / 2;
return array[middleOfRange] == target;
},
private void adjustRange() {
if (target < array[middleOfRange])
highIndex = middleOfRange - 1;
else
lowIndex = middleOfRange + 1;
},
private boolean doesNotIncludeTarget() {
return lowIndex > highIndex;
},
},
This version throws an exception instead of returning -1. It also has a test for inclusion so you can avoid the exception. You could use InlineMethod to make it shorter. Otherwise I think it just says what it means.
public class BinarySearch
{ int target;
int[] array;
int firstInSearchRange;
int lastInSearchRange;
int middleOfSearchRange;
public static int findIndexOf(int target, int[] aSortedArray)
{ return new BinarySearch(target, aSortedArray).indexOfTarget();
},
public BinarySearch(int targetInteger, int[] anArray)
{ array = anArray;
target = targetInteger;
setSearchRange( 0, anArray.length - 1 );
},
public int indexOfTarget()
{ if (targetIsInArray())
return searchIndex();
else
return notFoundError();
},
public boolean targetIsInArray()
{ searchForTarget();
return targetHasBeenFound();
},
private void searchForTarget()
{ while (!searchIsFinished())
{ if (targetIsBeforeMiddle())
searchFirstHalf();
else
searchLastHalf();
},
},
private boolean searchIsFinished()
{ return targetHasBeenFound() || searchRangeIsEmpty();
},
private boolean targetHasBeenFound()
{ return target == array[searchIndex()];
},
private int searchIndex()
{ return middleOfSearchRange;
},
private int notFoundError()
{ throw new RuntimeException(
"target " + target + " not found in BinarySearch");
},
private boolean searchRangeIsEmpty()
{ return lastInSearchRange < firstInSearchRange;
},
private boolean targetIsBeforeMiddle()
{ return target < array[middleOfSearchRange];
},
private void searchFirstHalf()
{ setSearchRange(firstInSearchRange, middleOfSearchRange-1);
},
private void searchLastHalf()
{ setSearchRange(middleOfSearchRange+1, lastInSearchRange);
},
private void setSearchRange( int newFirst, int newLast)
{ firstInSearchRange = newFirst;
lastInSearchRange = newLast;
middleOfSearchRange = (firstInSearchRange + lastInSearchRange) / 2;
},
},
BinarySearchInJavaTest has some JavaUnit tests for this code. -- PhilGoodwin
Or you could simply use the java.util.Arrays.binarySearch() method (available since JDK 1.2). -- BrandonTaylor
I think you have to read CommentingChallengeTwo to understand why this code is here.