public class CountingSearch
1: import java.util.Arrays;
2: import java.util.Random;
4: public class CountingSearch {
6: public static final Random RAND = new Random();
8: public static void main(String[] args) {
9: long countLS, countSLS, countBS;
10: int[] numbers;
11: int target;
13: // get started
14: printIntroduction();
15: numbers = makeIntArray();
16: target = getTarget();
18: // count ops in linear search
19: countLS = linearSearch(numbers, target);
21: // sort array for later searches
22: Arrays.sort(numbers);
24: // count ops in sorted linear search
25: countSLS = sortedLinearSearch(numbers, target);
27: // count ops in binary search
28: countBS = binarySearch(numbers, target);
30: // report results
31: System.out.println();
32: System.out.println("Counting Results:");
33: System.out.printf("%25s: %,20d%n", "Linear Search", countLS);
34: System.out.printf("%25s: %,20d%n", "Sorted Linear Search", countSLS);
35: System.out.printf("%25s: %,20d%n", "Binary Search", countBS);
36: System.out.println();
37: }
39: // print an introduction
40: private static void printIntroduction() {
41: System.out.println("\n"
42: + "Comparing Operation Counts\n"
43: + "--------------------------\n\n"
44: + "This program compares the number of steps it takes "
45: + "to search a large array for a\ntarget number. "
46: + "Run it multiple counts to see "
47: + "how little the count data varies.");
48: }
50: // make a large array of large numbers
51: private static int[] makeIntArray() {
52: int[] result = new int[100000];
53: for (int i = 0; i < result.length; ++i) {
54: result[i] = getTarget();
55: }
56: return result;
57: }
59: // generate a lanrge number randomly
60: private static int getTarget() {
61: return RAND.nextInt(0, Integer.MAX_VALUE);
62: }
64: // doa linear search of an unsorted array
65: private static int linearSearch(int[] numbers, int target) {
66: int count = 0;
67: for (int number : numbers) {
68: ++count;
69: if (number == target) {
70: return count;
71: }
72: }
73: return count;
74: }
76: // search a sorted array for a value, linearly
77: private static int sortedLinearSearch(int[] numbers, int target) {
78: int count = 0;
79: for (int number : numbers) {
80: ++count;
81: int diff = number - target;
82: if (diff == 0) {
83: return count;
84: } else if (diff > 0) {
85: return count;
86: }
87: }
88: return count;
89: }
91: /// search an array for a value using binary splits
92: private static int binarySearch(int[] numbers, int target) {
93: int count = 0;
94: int low = 0;
95: int high = numbers.length;
96: while (low < high) {
97: int mid = low + (high - low) / 2;
98: ++count;
99: int diff = target - numbers[mid];
100: if (diff < 0) {
101: // target is smaller
102: high = mid;
103: } else if (diff > 0) {
104: // target is larger
105: low = mid + 1;
106: } else {
107: return count;
108: }
109: }
110: return count;
111: }
113: }