Binary Search In Java

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.


CategoryJava

EditText of this page (last edited October 9, 2001) or FindPage with title or text search