Computer Science 210
Data Structures
Fall 2016, Siena College
BinSearch BlueJ Project
Click here to download a BlueJ project for BinSearch.
BinSearch Source Code
The Java source code for BinSearch is below. Click on a file name to download it.
/*
$Id: BinSearch.java 926 2009-09-28 01:53:05Z terescoj $
*/
/**
Sample methods for binary search: one for int values only,
one that uses Comparable Object references.
@author Jim Teresco, jteresco@mtholyoke.edu, jteresco@siena.edu
Original based on example code by Williams College faculty, used
and extended by Jim Teresco at Williams College, Mount Holyoke
College, The College of Saint Rose, and Siena College
*/
import java.util.Random;
public class BinSearch {
/**
Binary search on an array of int
@param a the input array
@param val int to find in the array
@pre a is sorted in ascending order
@return index of val in a, or -1 if not found
*/
public static int search (int[] a, int val) {
return binsearch(a, 0, a.length-1, val);
}
/**
Helper method to support additional parameters needed by
the recursive binary search on array of int
@param a the entire input array
@param low lowest index where val may be found
@param high highest index where val may be found
@param val int to find in the array
@return index of val in a, or -1 if not found
*/
protected static int binsearch(int[] a, int low, int high, int val) {
// is there still a range where we need to search?
if (low <= high) {
// compute the middle location of the range, where we
// will look for our element
int mid = (low + high) / 2;
if (val < a[mid]) {
// val is smaller than the element at the midpoint,
// so it could only be found in the first half.
// The following recursive call looks exactly there:
// from the bottom of our search range up to but
// not including the midpoint position (which we know
// doesn't contain val)
return binsearch(a, low, mid - 1, val);
}
else if (a[mid] < val) {
// Same idea: val is larger than the midpoint, so it
// could only be in second half, so we make an
// appropriate recursive call
return binsearch(a, mid + 1, high, val);
}
else {
// it wasn't too small, and it wasn't too big, so
// we found val at a[mid]! Return the index.
return mid;
}
}
else {
// there's no range left to search, so report that
// we didn't find val by returning -1
return -1;
}
}
/**
Binary search on an array of Comparable objects
@param a the input array
@param val the Comparable value to find in the array
@pre all elements in a and val must implement Comparable
@pre a is sorted in ascending order
@return index of val in a, or -1 if not found
*/
public static <T extends Comparable> int search (T[] a, T val) {
return binsearch(a, 0, a.length -1, val);
}
/**
Helper method for binary search on array of Comparables
@param a the entire input array
@param low lowest index where val may be found
@param high highest index where val may be found
@param val Comparable element to find in the array
@return index of val in a, or -1 if not found
*/
protected static <T extends Comparable> int binsearch(T[] a, int low, int high, T val) {
if (low <= high) {
// there is still a range of indices to search
int mid = (low + high) / 2;
if (val.compareTo(a[mid]) < 0) {
// value at midpoint too large, search first half
return binsearch(a, low, mid - 1, val);
}
else if (a[mid].compareTo(val) < 0) {
// value at midpoint too small, search second half
return binsearch(a, mid + 1, high, val);
}
else {
// it's at the midpoint
return mid;
}
}
else {
// the search range has no elements, so val can't be here
return -1;
}
}
/**
Example usage of the binary search methods
*/
public static void main(String[] args) {
Random r = new Random();
final int NUM_INTS = 100;
final int MAX_INCREMENT = 10;
int[] orderedInts = new int[NUM_INTS];
Integer[] orderedIntegers = new Integer[NUM_INTS];
// we'll put some random but ascending numbers into our arrays
int val = r.nextInt(MAX_INCREMENT) + 1;
orderedInts[0] = val;
orderedIntegers[0] = val; // will be autoboxed
for (int i = 1; i < NUM_INTS; i++) {
val = orderedInts[i-1] + r.nextInt(MAX_INCREMENT) + 1;
orderedInts[i] = val;
orderedIntegers[i] = val;
}
// print it
System.out.println("Array to search:");
for (int n : orderedInts) {
System.out.print(n + " ");
}
System.out.println();
// let's see which multiples of half the increment are here
// so we should have some matches and some not -- note
// we know the first will be a search for a value (0) which
// is smaller than all in the array, and the last will be
// larger than the last (largest) value
for (int i = 0;
i <= orderedInts[NUM_INTS-1] + MAX_INCREMENT;
i += MAX_INCREMENT/2) {
System.out.println("Searching for " + i + ": int array: " +
search(orderedInts, i) + ", Integer array: " +
search(orderedIntegers, i));
}
// the great thing is that we can create arrays of other kinds
// as well, as long as they're Comparables
// note these elements will each be autoboxed from double to Double
Double[] orderedDoubles = { -10.5, -6.0, 0.0, 3.5, 9.1, 17.23 };
System.out.println("Search for Double values, array to search:");
for (double n : orderedDoubles) {
System.out.print(n + " ");
}
System.out.println();
System.out.println("Search for -5.0: " + search(orderedDoubles, -5.0));
System.out.println("Search for 0.0: " + search(orderedDoubles, 0.0));
System.out.println("Search for 5.0: " + search(orderedDoubles, 5.0));
System.out.println("Search for 9.1: " + search(orderedDoubles, 9.1));
// and Strings work too
String[] orderedStrings = {
"Alice", "Bob", "Carol", "David", "Ellen", "Frank", "Gloria",
"Hal", "Isabelle", "Joey", "Kimberly", "Larry" };
System.out.println("Search for String values, array to search:");
for (String s : orderedStrings) {
System.out.print(s + " ");
}
System.out.println();
System.out.println("Search for Abby: " + search(orderedStrings, "Abby"));
System.out.println("Search for Carol: " + search(orderedStrings, "Carol"));
System.out.println("Search for Joey: " + search(orderedStrings, "Joey"));
System.out.println("Search for Zachary: " + search(orderedStrings, "Zachary"));
}
}