public class Searching
2: import java.util.ArrayList;
3: import java.util.Collections;
4: import java.util.List;
5: import java.util.Scanner;
7: /**
8: * Binary Search demonstration.
9: *
10: * @author Mark Young (A00000000)
11: */
12: public class Searching {
14: public static final Scanner kbd = new Scanner(System.in);
16: public static void main(String[] args) {
17: int numElts, eltToFind, position;
18: int biggest;
19: List<Integer> list = new ArrayList<>();
21: System.out.print("\n\n"
22: + "Binary Search\n"
23: + "-------------\n\n"
24: + "This program demonstrates using the binary search algorithm "
25: + "on a list of integers.\n\n");
27: // create a list
28: System.out.print("How long should I make the list? ");
29: numElts = kbd.nextInt();
30: kbd.nextLine();
32: // choosing the biggest number to be twice the length of the list will
33: // give a 50% chance of the chosen number being in the list.
34: biggest = 2 * numElts;
36: // create and sort the list
37: for (int i = 0; i < numElts; i++) {
38: list.add((int) (biggest * Math.random()));
39: }
40: Collections.sort(list);
42: // choose a random value to search for
43: eltToFind = (int) (biggest * Math.random());
44: System.out.println("\nWe're going to search for " + eltToFind);
45: pause();
47: // search
48: position = binarySearch(list, eltToFind);
50: // report the results
51: if (position < 0) {
52: System.out.println(eltToFind + " is not in the list");
53: } else {
54: System.out.println(eltToFind + " is in position #" + position);
55: System.out.println("list.get(" + position + ") == "
56: + list.get(position));
57: }
58: pause();
59: }
61: /**
62: * Search a sorted list for the given element. Print out the steps of the
63: * search.
64: *
65: * @param list the list to search (must be sorted)
66: * @param value the value to search for
67: * @return the position of value in list, or a negative number if it's not
68: * there
69: */
70: public static int binarySearch(List<Integer> list, int value) {
71: return binarySearch(list, value, 0, list.size());
72: }
74: /**
75: * Search part of a sorted list for the given element. Print out the steps
76: * of the search.
77: *
78: * @param list the list to search (must be sorted)
79: * @param value the value to search for
80: * @param lo the lowest position to search
81: * @param hi one more than the highest position to search
82: * @return the position of value in list, or a negative number if it's not
83: * in the given range
84: */
85: private static int binarySearch(List<Integer> list,
86: int value, int lo, int hi) {
87: // report how the search is going
88: System.out.println("Searching for " + value + " in:");
89: printList(list, lo, hi);
90: // You might want to comment out that code for long lists!
92: // do the search
93: if (lo == hi) { // ran out of places to look
94: // report running out of places to look
95: System.out.println("Ran out of places to look!");
96: pause();
98: return -1;
99: } else {
100: int mid = lo + (hi - lo) / 2;
101: System.out.println("The midpoint value is " + list.get(mid));
102: pause();
103: if (list.get(mid) == value) { // found it!
104: return mid;
105: } else if (value < list.get(mid)) { // look below
106: return binarySearch(list, value, lo, mid);
107: } else { // look above
108: return binarySearch(list, value, mid + 1, hi);
109: }
110: }
111: }
113: /**
114: * number of numbers printed per line
115: */
116: private static final int PER_LINE = 8;
117: /**
118: * number of spaces per number
119: */
120: private static final int SPACES = 79 / PER_LINE;
121: /**
122: * format string for numbers
123: */
124: private static final String NUM_FORMAT = "%," + SPACES + "d";
125: /**
126: * format string for place fillers
127: */
128: private static final String STR_FORMAT = "%" + SPACES + "s";
130: /**
131: * Print a list showing only the numbers in one part of it. Numbers before
132: * the starting point/after the ending point are replaced with "filler".
133: *
134: * @param list the list to print
135: * @param lo positions less than lo are "filled"
136: * @param hi positions hi and greater are "filled"
137: */
138: private static void printList(List<Integer> list, int lo, int hi) {
139: int thisLine = 0;
140: for (int i = 0; i < list.size(); i++) {
141: if (thisLine == PER_LINE) {
142: System.out.println();
143: thisLine = 0;
144: }
145: if (lo <= i && i < hi) {
146: System.out.printf(NUM_FORMAT, list.get(i));
147: } else {
148: System.out.printf(STR_FORMAT, "...");
149: }
150: ++thisLine;
151: }
152: System.out.println();
153: }
155: /**
156: * Wait for the user to press the enter key.
157: */
158: public static void pause() {
159: System.out.print("\n...Press ENTER...");
160: kbd.nextLine();
161: System.out.println();
162: }
164: }