public class NameFinderWithError
1: //NameFinderWithError.java
2: //Note: In this program "position" is really "index".
3: /*
4: * Run the recursive program, and observe the output statements
5: * for debugging, and that the person is correctly not found.
6: *
7: * Introduce an error by changing itemPos = -1 to itemPos = 0
8: * in the range size == 1 base case.
9: *
10: * Run the program, notice how the indented print statements help
11: * isolate the error of the person incorrectly being found.
12: */
14: import java.util.Scanner;
15: import java.util.ArrayList;
17: public class NameFinderWithError
18: {
19: /* Finds index of string in vector of strings, else -1.
20: Searches only with index range low to high
21: Note: Upper/lower case characters matter
22: */
23: public static int findMatch
24: (
25: ArrayList<String> stringList,
26: String itemMatch,
27: int lowVal,
28: int highVal,
29: String indentAmt // indentAmt used for print debug
30: )
31: {
32: int midVal; // Midpoint of low and high values
33: int itemPos; // Position where item found, -1 if not found
34: int rangeSize; // Remaining range of values to search for match
36: System.out.println
37: (
38: indentAmt + "Find() range " + lowVal + " " + highVal
39: );
40: rangeSize = (highVal - lowVal) + 1;
41: midVal = (highVal + lowVal) / 2;
43: if (itemMatch.equals(stringList.get(midVal)))
44: {
45: // Base case 1: item found at midVal position
46: System.out.println(indentAmt + "Found person.");
47: itemPos = midVal;
48: }
49: else if (rangeSize == 1)
50: {
51: // Base case 2: match not found
52: System.out.println(indentAmt + "Person not found.");
53: itemPos = -1;
54: }
55: else // Recursive case: search lower or upper half
56: {
57: if (itemMatch.compareTo(stringList.get(midVal)) < 0)
58: {
59: // Search lower half, recursive call
60: System.out.println(indentAmt + "Searching lower half.");
61: itemPos = findMatch
62: (
63: stringList,
64: itemMatch,
65: lowVal,
66: midVal,
67: indentAmt + " "
68: );
69: }
70: else // Search upper half, recursive call
71: {
72: System.out.println(indentAmt + "Searching upper half.");
73: itemPos = findMatch
74: (
75: stringList,
76: itemMatch,
77: midVal + 1,
78: highVal,
79: indentAmt + " "
80: );
81: }
82: }
84: System.out.println(indentAmt + "Returning pos = " + itemPos + ".");
85: return itemPos;
86: }
88: public static void main(String[] args)
89: {
90: Scanner scnr = new Scanner(System.in);
91: // List of attendees
92: ArrayList<String> attendeesList = new ArrayList<String>();
93: String attendeeName; // Name of attendee to match
94: int matchPos; // Matched position in attendee list
96: // Omitting part of program that adds attendees
97: // Instead, we insert some sample attendees in sorted order
98: attendeesList.add("Adams, Mary");
99: attendeesList.add("Carver, Michael");
100: attendeesList.add("Domer, Hugo");
101: attendeesList.add("Fredericks, Carlos");
102: attendeesList.add("Li, Jie");
104: // Prompt user to enter a name to find
105: System.out.print("Enter person's name: Last, First: ");
106: // Use nextLine() to allow space in name
107: attendeeName = scnr.nextLine();
109: // Call function to match name, output results
110: matchPos = findMatch(attendeesList, attendeeName, 0,
111: attendeesList.size() - 1, " ");
112: if (matchPos >= 0)
113: {
114: System.out.println("Found at position " + matchPos + ".");
115: }
116: else
117: {
118: System.out.println("Not found.");
119: }
120: }
121: }