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