Source of BinarySearch.java



  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: }