// File: BinarySearcher.java
// A Java application to illustrate the binary search of an array.
// Additional javadoc documentation is available at
// http://www.cs.colorado.edu/~main/docs/BinarySearcher.html
/******************************************************************************
* The BinarySearcher
Java application runs a small test on the
* search
method from Chapter 11 (using a binary search to
* find a specified number in an array).
*
*
Java Source Code for this class:
*
* http://www.cs.colorado.edu/~main/applications/SimpleSearcher.java
*
*
* @author Michael Main
* (main@colorado.edu)
*
* @version Feb 10, 2016
******************************************************************************/
public class BinarySearcher
{
/**
* The main method prints a table of test results, searching for numbers
* in an array that contains 2, 4, 6, 8, 10, 12, and 14.
* @param args
* not used in this implementation
**/
public static void main(String[ ] args)
{
final int[ ] DATA = { 2, 4, 6, 8, 10, 12, 14 };
final int[ ] EMPTY = new int[0];
final int MINIMUM = -1;
final int MAXIMUM = 16;
int target;
int answer;
System.out.println("Searching for numbers in an array.");
for (target = MINIMUM; target <= MAXIMUM; target++)
{
System.out.print("Is " + target + " in the array? ");
answer = search(DATA, 0, DATA.length, target);
if (answer == -1)
System.out.println("No.");
else
System.out.println("Yes, at index [" + answer + "].");
}
System.out.print("Searching for 0 in an empty array: ");
if (search(EMPTY, 0, 0, 0) == -1)
System.out.println(" Not found.");
else
System.out.println(" Found!");
System.out.println("End of searching.");
}
/**
* Search part of a sorted array for a specified target.
* @param a
* the array to search
* @param first
* the first index of the part of the array to search
* @param size
* the number of elements to search, starting at
* a[first]
* @param target
* the element to search for
* Precondition:
* If size > 0
, then first
through
* first+size-1
must be valid indexes for the array a
.
* Also, starting at a[first]
, the next size
* elements are sorted in increasing order from small to large.
* @return
* If target
appears in the array segment starting at
* a[first]
and containing size
elements,
* then the return value is the index of a location that
* contains target
; otherwise the return value is -1.
* @exception ArrayIndexOutOfBoundsException
* Indicates that some index in the range first
* through first+size-1
is outside the range of
* valid indexes for the array a
.
**/
public static int search(int[ ] a, int first, int size, int target)
{
int middle;
if (size <= 0)
return -1;
else
{
middle = first + size/2;
if (target == a[middle])
return middle;
else if (target < a[middle])
// The target is less than a[middle], so search before the middle.
return search(a, first, size/2, target);
else
// The target must be greater than a[middle], so search after the middle.
return search(a, middle+1, (size-1)/2, target);
}
}
}