program performs a binary search on an array of last names, and if a match is found, returns the phone number from a parallel array.

Flowgorithm help please!!

program performs a binary search on an array of last names, and if a match is found, returns the phone number from a parallel array. There is a Main module and a function called  binarySearch(), which returns the array index of the found item, or -1 if a match is not found.

You can create the program in Flowgorithm by following the pseudocode in the book for Program 9-8. There are a few new things, but none of them are difficult.

·       Constants, which can be simulated by using Integer variables spelled with upper case letters

·       String variables and String arrays, whose values must be entered with double quotes around them

·       A Boolean variable (found), which indicates if a match has been found

It is important that you understand the logic of the binary search. You pick a middle point in a sorted array. If the value you are trying to match is lower than the middle value, you eliminate the top half of the array (by resetting the first pointer to one position after the middle). If the value you are trying to match is higher than the middle value, you eliminate the bottom half of the array (by resetting the last pointer to one position before the middle). You continue to search in the new “half array”, until a match is found, or you have determined that the match does not exist.

In this program, you will set up a sorted String array of last names, and a parallel String array of corresponding phone numbers. You will enter a last name to look for, and the program will tell you the person’s phone number if a match was found, or an error message if a match was not found.

ASSIGNMENT: Start Flowgorithm, and then do the assignment outlined in step 2. Save the Flowgorithm file on your flash drive or PC as S10.fprg. Submit the Flowgorithm file in Blackboard.

1)    Create Flowgorithm program as follows.

a.     Include the usual comment lines for Author, Date and Description.

b.     Declare the constant  SIZE  as an Integer variable, and assign the value 6.

c.     Declare the two String arrays to a size of SIZE, and use individual assignment statements to set their values (names[0] = “Hall”, etc.). This takes some time to type, but you’ll be pleased when you get it working!

d.     Remember that you have to declare and assign variables in separate steps.

e.     You will write a function called  binarySearch()  with three arguments just as specified in line 31. It will return an Integer value named  position,  which is declared in line 62 and initially set to -1.

f.      Flowgorithm accepts both the C and Visual Basic operators, so you can specify “not found” as  NOT found, or you can specify it as  !found

g.     Be careful with your spelling and punctuation. Each non-comment line in this Flowgorithm program can be entered from the pseudocode in the book.

h.    Run the program with the input on page 371. Your output in the Console window should show the same values as the textbook. The screen shot below is from running the program with that input data.

i.      If there are any errors, recheck the instructions and correct them, then resave the file.

DEBUGGING THE PROGRAM: One of the greatest skills a programmer can develop is debugging, which means locating and fixing errors in a program. Please attach your Flowgorithm file (S10.fprg) to your email

 1 Module main()

 2    // Constant for array sizes

 3    Constant Integer SIZE = 6

 4

 5    // Array of instructor names, already sorted in

 6    // ascending order.

 7    Declare String names[SIZE] = “Hall”, “Harrison”,

 8                                 “Hoyle”, “Kimura”,

 9                                 “Lopez”, “Pike”

10

11    // Parallel array of instructor phone numbers.

12    Declare String phones[SIZE] = “555-6783”, “555-0199”,

13                                  “555-9974”, “555-2377”,

14                                  “555-7772”, “555-1716”

15

16    // Variable to hold the last name to search for.

17    Declare String searchName

18

19    // Variable to hold the subscript of the name.

20    Declare Integer index

21

22    // Variable to control the loop.

23    Declare String again = “Y”

24

25    While (again == “Y” OR again == “y”)

26      // Get the name to search for.

27      Display “Enter a last name to search for.”

28      Input searchName

29

30      // Search for the last name.

31      index = binarySearch(names, searchName, SIZE)

32

33      If index ! = -1 Then

34         // Display the phone number.

35         Display “The phone number is “, phones[index]

36      Else

37         // The name was not found in the array.

38         Display searchName, ” was not found.”

39      End If

40

41      // Search again?

42      Display “Do you want to search again? (Y=Yes, N=No)”

43      Input again

44    End While

45

46 End Module

47

48 // The binarySearch function accepts as arguments a String

49 // array, a value to search the array for, and the size

50 // of the array. If the value is found in the array, its

51 // subscript is returned. Otherwise, -1 is returned,

52 // indicating that the value was not found in the array.

53 Function Integer binarySearch(String array[], String value,

54                               Integer arraySize)

55     // Variable to hold the subscript of the first element.

56     Declare Integer first = 0

57

58    // Variable to hold the subscript of the last element.

59    Declare Integer last = arraySize – 1

60

61    // Position of the search value

62    Declare Integer position = -1

63

64    // Flag

65    Declare Boolean found = False

66

67    // Variable to hold the subscript of the midpoint.

68    Declare Integer middle

69

70    While (NOT found) AND (first <= last)

71      // Calculate the midpoint.

72      Set middle = (first + last) / 2

73

74      // See if the value is found at the midpoint…

75      If array[middle] == value Then

76         Set found = True

77         Set position = middle

78

79      // Else, if the value is in the lower half…

80      Else If array[middle] > value Then

81         Set last = middle – 1

82

83      // Else, if the value is in the upper half…

84      Else

85         Set first = middle + 1

86      End If

87    End While

88

89  // Return the position of the item, or -1

90  // if the item was not found.

91  Return position

92 End Function

Program Output (with Input Shown in Bold)

Enter a last name to search for.

Lopez [Enter]

The phone number is 555-7772

Do you want to search again? (Y=Yes, N=No)

Y [Enter]

Enter a last name to search for.

Harrison [Enter]

The phone number is 555-0199

Do you want to search again? (Y=Yes, N=No)

Y [Enter]

Enter a last name to search for.

Lee [Enter]

Lee was not found.

Do you want to search again? (Y=Yes, N=No)

N [Enter]