SortedSearch.java
SortedSearch.java
— 11.5 KB
Dateiinhalt
import java.util.Comparator;
import java.util.Random;
public class SortedSearch {
public static abstract class Search {
protected CountingComparator comparator;
public Search() {
this.comparator = new CountingComparator();
}
public abstract boolean search(Long[] sortedList, Long key);
public int getNumberOfComparisons() {
return this.comparator.getNumberOfComparisons();
}
}
public static class LinearSearch extends Search {
@Override
public boolean search(Long[] sortedList, Long key) {
for (Long element : sortedList) {
// compare returns a negative integer, zero, or a positive integer if
// the first argument is less than, equal to, or greater than the
// second.
int comparison = this.comparator.compare(element, key);
if (comparison == 0) {
return true;
}
}
return false;
}
}
public static class BinarySearch extends Search {
@Override
public boolean search(Long[] sortedList, Long key) {
// TODO: Code hier einfuegen
return false;
}
}
public static class InterpolationSearch extends Search {
@Override
public boolean search(Long[] sortedList, Long key) {
// TODO: Code hier einfuegen
return false;
}
}
public static class FibonacciSearch extends Search {
@Override
public boolean search(Long[] sortedList, Long key) {
// TODO: Code hier einfuegen
return false;
}
}
public static class CountingComparator implements Comparator<Long> {
private int numberOfComparisons;
public CountingComparator() {
this.numberOfComparisons = 0;
}
@Override
public int compare(Long o1, Long o2) {
this.numberOfComparisons++;
return o1.compareTo(o2);
}
public int getNumberOfComparisons() {
return this.numberOfComparisons;
}
}
public static void main(String[] args) {
Search search;
Random random = new Random(1l);
System.out.println("Preliminary testing. Initializing list [1, 2, 3].");
Long[] list = { 1l, 2l, 3l };
System.out.println("Searching for Element \"0\", which should not be found.");
search = new LinearSearch();
boolean located = search.search(list, 0l);
System.out.println("\tLinear search: " + (located ? "located" : "did not locate")
+ " element \"0\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new BinarySearch();
located = search.search(list, 0l);
System.out.println("\tBinary search: " + (located ? "located" : "did not locate")
+ " element \"0\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new FibonacciSearch();
located = search.search(list, 0l);
System.out.println("\tFibonacci search: " + (located ? "located" : "did not locate")
+ " element \"0\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new InterpolationSearch();
located = search.search(list, 0l);
System.out.println("\tInterpolation search: " + (located ? "located" : "did not locate")
+ " element \"0\" (" + search.getNumberOfComparisons() + " comparisons).");
System.out.println("Searching for Element \"1\", which should be found.");
search = new LinearSearch();
located = search.search(list, 1l);
System.out.println("\tLinear search: " + (located ? "located" : "did not locate")
+ " element \"1\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new BinarySearch();
located = search.search(list, 1l);
System.out.println("\tBinary search: " + (located ? "located" : "did not locate")
+ " element \"1\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new FibonacciSearch();
located = search.search(list, 1l);
System.out.println("\tFibonacci search: " + (located ? "located" : "did not locate")
+ " element \"1\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new InterpolationSearch();
located = search.search(list, 1l);
System.out.println("\tInterpolation search: " + (located ? "located" : "did not locate")
+ " element \"1\" (" + search.getNumberOfComparisons() + " comparisons).");
System.out.println("Searching for Element \"2\", which should be found.");
search = new LinearSearch();
located = search.search(list, 2l);
System.out.println("\tLinear search: " + (located ? "located" : "did not locate")
+ " element \"2\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new BinarySearch();
located = search.search(list, 2l);
System.out.println("\tBinary search: " + (located ? "located" : "did not locate")
+ " element \"2\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new FibonacciSearch();
located = search.search(list, 2l);
System.out.println("\tFibonacci search: " + (located ? "located" : "did not locate")
+ " element \"2\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new InterpolationSearch();
located = search.search(list, 2l);
System.out.println("\tInterpolation search: " + (located ? "located" : "did not locate")
+ " element \"2\" (" + search.getNumberOfComparisons() + " comparisons).");
System.out.println("Searching for Element \"3\", which should be found.");
search = new LinearSearch();
located = search.search(list, 3l);
System.out.println("\tLinear search: " + (located ? "located" : "did not locate")
+ " element \"3\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new BinarySearch();
located = search.search(list, 3l);
System.out.println("\tBinary search: " + (located ? "located" : "did not locate")
+ " element \"3\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new FibonacciSearch();
located = search.search(list, 3l);
System.out.println("\tFibonacci search: " + (located ? "located" : "did not locate")
+ " element \"3\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new InterpolationSearch();
located = search.search(list, 3l);
System.out.println("\tInterpolation search: " + (located ? "located" : "did not locate")
+ " element \"3\" (" + search.getNumberOfComparisons() + " comparisons).");
System.out.println("Searching for Element \"4\", which should not be found.");
search = new LinearSearch();
located = search.search(list, 4l);
System.out.println("\tLinear search: " + (located ? "located" : "did not locate")
+ " element \"4\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new BinarySearch();
located = search.search(list, 4l);
System.out.println("\tBinary search: " + (located ? "located" : "did not locate")
+ " element \"4\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new FibonacciSearch();
located = search.search(list, 4l);
System.out.println("\tFibonacci search: " + (located ? "located" : "did not locate")
+ " element \"4\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new InterpolationSearch();
located = search.search(list, 4l);
System.out.println("\tInterpolation search: " + (located ? "located" : "did not locate")
+ " element \"4\" (" + search.getNumberOfComparisons() + " comparisons).");
System.out
.println("\nInitializing pseudo-randomized, sorted list with one million elements. The list starts with a zero and neighboring elements have a difference of 1-3.");
list = new Long[1000000];
list[0] = 0l;
for (int i = 1; i < list.length; i++) {
list[i] = list[i - 1] + random.nextInt(3) + 1;
}
System.out.println("Searching for Element \"0\", which should be the first element.");
search = new LinearSearch();
located = search.search(list, 0l);
System.out.println("\tLinear search: " + (located ? "located" : "did not locate")
+ " element \"0\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new BinarySearch();
located = search.search(list, 0l);
System.out.println("\tBinary search: " + (located ? "located" : "did not locate")
+ " element \"0\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new FibonacciSearch();
located = search.search(list, 0l);
System.out.println("\tFibonacci search: " + (located ? "located" : "did not locate")
+ " element \"0\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new InterpolationSearch();
located = search.search(list, 0l);
System.out.println("\tInterpolation search: " + (located ? "located" : "did not locate")
+ " element \"0\" (" + search.getNumberOfComparisons() + " comparisons).");
System.out.println("Searching for the 300.000th element of the list.");
search = new LinearSearch();
located = search.search(list, list[300000 - 1]);
System.out.println("\tLinear search: " + (located ? "located" : "did not locate")
+ " element \"" + list[300000 - 1].intValue() + "\" (" + search.getNumberOfComparisons()
+ " comparisons).");
search = new BinarySearch();
located = search.search(list, list[300000 - 1]);
System.out.println("\tBinary search: " + (located ? "located" : "did not locate")
+ " element \"" + list[300000 - 1].intValue() + "\" (" + search.getNumberOfComparisons()
+ " comparisons).");
search = new FibonacciSearch();
located = search.search(list, list[300000 - 1]);
System.out.println("\tFibonacci search: " + (located ? "located" : "did not locate")
+ " element \"" + list[300000 - 1].intValue() + "\" (" + search.getNumberOfComparisons()
+ " comparisons).");
search = new InterpolationSearch();
located = search.search(list, list[300000 - 1]);
System.out.println("\tInterpolation search: " + (located ? "located" : "did not locate")
+ " element \"" + list[300000 - 1].intValue() + "\" (" + search.getNumberOfComparisons()
+ " comparisons).");
System.out
.println("\nInitializing list with 63 elements. The list starts with a one and following elements have 2 times the value of its predecessor.");
list = new Long[63];
list[0] = 1l;
for (int i = 1; i < list.length; i++) {
list[i] = list[i - 1] * 2l;
}
System.out.println("Searching for Element \"2^31\", which should be right in the middle.");
search = new LinearSearch();
located = search.search(list, (long) Math.pow(2d, 31d));
System.out.println("\tLinear search: " + (located ? "located" : "did not locate")
+ " element \"2^31\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new BinarySearch();
located = search.search(list, (long) Math.pow(2d, 31d));
System.out.println("\tBinary search: " + (located ? "located" : "did not locate")
+ " element \"2^31\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new FibonacciSearch();
located = search.search(list, (long) Math.pow(2d, 31d));
System.out.println("\tFibonacci search: " + (located ? "located" : "did not locate")
+ " element \"2^31\" (" + search.getNumberOfComparisons() + " comparisons).");
search = new InterpolationSearch();
located = search.search(list, (long) Math.pow(2d, 31d));
System.out.println("\tInterpolation search: " + (located ? "located" : "did not locate")
+ " element \"2^31\" (" + search.getNumberOfComparisons() + " comparisons).");
}
}