public class BinarySearch
3: import java.util.Arrays;
4: import java.util.Scanner;
6: /**
7: *
8: * @author Mark Young (A00000000)
9: */
10: public class BinarySearch {
12: public static final Scanner KBD = Common.KBD;
13: private static final int HOW_MANY = 40;
14: private static final int MAX = 100;
15: private static int traceLevel = 0;
17: public static void main(String[] args) {
18: System.out.println("\n\n"
19: + "Binary Search\n"
20: + "=============\n");
22: setTraceLevel();
24: // create an array of random integers
25: int[] numbers = Common.randomNumbers(HOW_MANY, MAX / 10, MAX);
26: Arrays.sort(numbers);
27: Common.printArray(numbers);
28: Common.pause();
30: // sort it
31: int value = Common.randomNumber(MAX / 10, MAX);
32: System.out.println("Searching for " + value + ":");
33: int posn = binarySearch(numbers, value);
35: // show result
36: if (posn >= 0) {
37: System.out.println(value + " found at " + posn + ":");
38: Common.printArray(numbers, posn, posn + 1);
39: } else {
40: System.out.println(value + " not found");
41: }
42: Common.pause();
43: }
45: /**
46: * Prompt for and read a level of tracing to do.
47: */
48: public static void setTraceLevel() {
49: String traceMenu = "Enter a trace level: \n"
50: + " 0 - no tracing\n"
51: + " 1 - tracing\n\n"
52: + "Trace level: ";
54: System.out.print(traceMenu);
55: traceLevel = KBD.nextInt();
56: KBD.nextLine();
57: while (traceLevel < 0 || 1 < traceLevel) {
58: System.out.print(traceMenu);
59: traceLevel = KBD.nextInt();
60: KBD.nextLine();
61: }
62: }
64: /**
65: * Search the given array.
66: *
67: * @param arr the array to search
68: * @param value the value to search for
69: */
70: public static int binarySearch(int[] arr, int value) {
71: int lo = 0;
72: int hi = arr.length;
73:
74: while (lo < hi) {
75: int mid = lo + (hi - lo) / 2;
76: if (traceLevel > 0) {
77: System.out.println("Searching for " + value + "...");
78: Common.printArray(arr, mid, mid + 1);
79: Common.pause();
80: }
81: if (value < arr[mid]) {
82: hi = mid;
83: } else if (arr[mid] < value) {
84: lo = mid + 1;
85: } else {
86: return mid;
87: }
88: }
89: return -1;
90: }
91: }