public class TimingSearch
1: import java.util.Arrays;
2: import java.util.Random;
4: public class TimingSearch {
6: public static final Random RAND = new Random();
8: public static void main(String[] args) {
9: long begin, timeLS, timeSLS, timeBS;
10: int[] numbers;
11: int target;
13: // get started
14: printIntroduction();
15: numbers = makeIntArray();
16: target = getTarget();
18: // time linear search
19: begin = System.nanoTime();
20: linearSearch(numbers, target);
21: timeLS = System.nanoTime() - begin;
23: // sort array for remaining searches
24: Arrays.sort(numbers);
26: // time sorted linear search
27: begin = System.nanoTime();
28: sortedLinearSearch(numbers, target);
29: timeSLS = System.nanoTime() - begin;
31: // time binary search
32: begin = System.nanoTime();
33: binarySearch(numbers, target);
34: timeBS = System.nanoTime() - begin;
36: // report results
37: System.out.println("Timing Results:");
38: System.out.printf("%25s: %,20d%n", "Linear Search", timeLS);
39: System.out.printf("%25s: %,20d%n", "Sorted Linear Search", timeSLS);
40: System.out.printf("%25s: %,20d%n", "Binary Search", timeBS);
41: }
43: // Print an introduction
44: private static void printIntroduction() {
45: System.out.println("\n"
46: + "Comparing Search Times\n"
47: + "----------------------\n\n"
48: + "This program compares the amount of time it takes "
49: + "to search a large array for a\ntarget number. "
50: + "Run it multiple times to see how the timing data varies.");
51: }
53: // Create a large array of large numbers
54: private static int[] makeIntArray() {
55: int[] result = new int[100000];
56: for (int i = 0; i < result.length; ++i) {
57: result[i] = getTarget();
58: }
59: return result;
60: }
62: // create a large number, randomly
63: private static int getTarget() {
64: return RAND.nextInt(0, Integer.MAX_VALUE);
65: }
67: // search an unsorted array for a value
68: private static boolean linearSearch(int[] numbers, int target) {
69: for (int number : numbers) {
70: if (number == target) {
71: return true;
72: }
73: }
74: return false;
75: }
77: // search a sorted array for a value, linearly
78: private static boolean sortedLinearSearch(int[] numbers, int target) {
79: for (int number : numbers) {
80: if (number == target) {
81: return true;
82: } else if (number > target) {
83: return false;
84: }
85: }
86: return false;
87: }
89: // search a sorted array for a value using binary split
90: private static boolean binarySearch(int[] numbers, int target) {
91: int low = 0;
92: int high = numbers.length;
93: while (low < high) {
94: int mid = low + (high - low) / 2;
95: int diff = target - numbers[mid];
96: if (diff < 0) {
97: // target is smaller
98: high = mid;
99: } else if (diff > 0) {
100: // target is larger
101: low = mid + 1;
102: } else {
103: return true;
104: }
105: }
106: return false;
107: }
109: }