// Program: Activity 8 - Module 9 - Searching
// Author: Steve Ellermann
// Class: CSC205
// Description: Driver for binary and interpolation search methods
import java.util.Random;
public class Activity8 {
public static void main(String[] args) {
Integer result;
Random rand = new Random();
Integer a[] = new Integer[5000];
Integer b[] = new Integer[5000];
// Uniform distribution
for (int ii = 0; ii < a.length; ii++) {
a[ii] = ii * 2;
}
// Non-uniform distribution
b[0] = 1;
for (int ii = 1; ii < b.length; ii++) {
b[ii] = (b[ii - 1] + rand.nextInt(20)) + ii * ii * 2;
}
int[] testValues = { -1, 1, 4, 41, 440, 8800, 9990, 1000000 };
System.out.println("UNIFORM DISTRIBUTION");
System.out.println("Binary Search:");
for (int x : testValues) {
System.out.print(" Searching for (" + x + "): ");
result = Searching.binarySearch(a, x);
System.out.print("\tbinary: " + result + " in " + Searching.getCounter() + " ");
result = Searching.interpolationSearch(a, x);
System.out.println("\t\t interpolation: " + result + " in " + Searching.getCounter());
}
System.out.println();
System.out.println("NON-UNIFORM DISTRIBUTION");
for (int x : testValues) {
System.out.print(" Searching for (" + x + "): ");
result = Searching.binarySearch(b, x);
System.out.print("\tbinary: " + result + " in " + Searching.getCounter() + " ");
result = Searching.interpolationSearch(b, x);
System.out.println("\t\t interpolation: " + result + " in " + Searching.getCounter());
}
}
}
// Program: Activity 8 - Module 9 - Searching
// Author: Steve Ellermann
// Class: CSC205
// Description: Linear (recursive), Binary (recursive), and
// Interpolation (recursive) search methods.
public class Searching {
private static int counter = 0;
// getCounter
public static int getCounter() {
return counter;
}
// setCounter
public static void setCounter(int counter) {
Searching.counter = counter;
}
// resetCounter
private static void resetCounter() {
setCounter(0);
}
// linearSearch
public static <T extends Comparable<T>> T linearSearch(T[] data, T target) {
return (linearSearch(data, 0, data.length - 1, target));
}
// linearSearch helper method
public static <T extends Comparable<T>> T linearSearch(T[] data, int min, int max, T target) {
T ret = null;
int current = min;
resetCounter();
while (current <= max) {
counter++;
if (data[current].compareTo(target) == 0) {
ret = data[current];
break;
}
current++;
}
return ret;
}
// binarySearch
public static <T extends Comparable<T>> T binarySearch(T[] data, T target) {
resetCounter();
return (binarySearch(data, 0, data.length - 1, target));
}
// binarySearch helper method
public static <T extends Comparable<T>> T binarySearch(T[] data, int min, int max, T target) {
T ret = null;
if (min > max) {
return null;
}
int mid = min + ((max - min) / 2);
counter++;
int comparisonResult = data[mid].compareTo(target);
if (comparisonResult == 0) {
ret = data[mid];
} else if (comparisonResult > 0) {
ret = binarySearch(data, min, mid - 1, target);
} else {
ret = binarySearch(data, mid + 1, max, target);
}
return ret;
}
// interpolationSearch - Works with integers. Works when the array is sorted.
public static <T extends Comparable<T>> Integer interpolationSearch(Integer[] data, int target) {
resetCounter();
return (interpolationSearch(data, 0, data.length - 1, target));
}
// interpolationSearch helper method - Works with integers. Works when the array is sorted.
public static <T extends Comparable<T>> Integer interpolationSearch(Integer[] data, int min,
int max, int target) {
int ret = -1;
if (min > max || (data[min] > target) || (target > data[max])) {
return -1;
}
int mid = (min + ((max - min) * (target - data[min])) / (data[max] - data[min]));
counter++;
int comparisonResult = data[mid].compareTo(target);
if (comparisonResult == 0) {
ret = data[mid];
} else if (comparisonResult > 0) {
ret = interpolationSearch(data, min, (mid - 1), target);
} else {
if (data.length > counter) { // prevents stack overflow
ret = interpolationSearch(data, (mid + 1), max, target);
}
}
return ret;
}
}
