public class NameFinder
1: //NameFinder.java
3: import java.util.Scanner;
4: import java.util.ArrayList;
6: public class NameFinder
7: {
8: /* Finds index of string in vector of strings, else -1.
9: Searches only with index range low to high
10: Note: Upper/lower case characters matter
11: */
12: public static int findMatch
13: (
14: ArrayList<String> stringList,
15: String itemMatch,
16: int lowVal,
17: int highVal
18: )
19: {
20: int midVal; // Midpoint of low and high values
21: int itemPos; // Position where item found, -1 if not found
22: int rangeSize; // Remaining range of values to search for match
24: rangeSize = (highVal - lowVal) + 1;
25: midVal = (highVal + lowVal) / 2;
27: if (itemMatch.equals(stringList.get(midVal)))
28: {
29: itemPos = midVal; // Base case 1: item found at midVal position
30: }
31: else if (rangeSize == 1)
32: {
33: itemPos = -1; // Base case 2: match not found
34: }
35: else // Recursive case: search lower or upper half
36: {
37: if (itemMatch.compareTo(stringList.get(midVal)) < 0)
38: {
39: // Search lower half, recursive call
40: itemPos =
41: findMatch(stringList, itemMatch, lowVal, midVal);
42: }
43: else
44: {
45: // Search upper half, recursive call
46: itemPos =
47: findMatch(stringList, itemMatch, midVal + 1, highVal);
48: }
49: }
51: return itemPos;
52: }
54: public static void main(String[] args)
55: {
56: Scanner scnr = new Scanner(System.in);
57: ArrayList<String> attendeesList = new
58: ArrayList<String>(); // List of attendees
59: String attendeeName; // Name of attendee to match
60: int matchPos; // Matched position in attendee list
62: // Omitting part of program that adds attendees
63: // Instead, we insert some sample attendees in sorted order
64: attendeesList.add("Adams, Mary");
65: attendeesList.add("Carver, Michael");
66: attendeesList.add("Domer, Hugo");
67: attendeesList.add("Fredericks, Carlos");
68: attendeesList.add("Li, Jie");
70: // Prompt user to enter a name to find
71: System.out.print("Enter person's name: Last, First: ");
72: // Use nextLine() to allow space in name
73: attendeeName = scnr.nextLine();
75: // Call function to match name, output results
76: matchPos = findMatch(attendeesList, attendeeName, 0,
77: attendeesList.size() - 1);
78: if (matchPos >= 0)
79: {
80: //System.out.println("Found at position " + matchPos + ".");
81: //Changed word "position" to "index" ...
82: System.out.println("Found at index " + matchPos + ".");
83: }
84: else
85: {
86: System.out.println("Not found.");
87: }
88: }
89: }