Binary Search

I. Objectives:
Practicing with Binary Search (Chapter 16) and Sorting Algorithms (Chapter 16 and Chapter 8)
Practicing writing a small-to-medium size program that is modularized (using functions) and deals with lists
II. Instructions:
You job is to write a menu-based program to manipulate a patient database in a hospital. I do not provide any skeleton code for this assignment. You will have to design all the data structures and program structure yourself. The designing of your program will be a big part of your grade in this assignment.
1. Your program should do the following
(a) Show the user a menu that has the following options.
1. Print patients
2. Add a patient
3. Sort patients by last name
4. Sort patients by ID
5. Search patient by last name
6. Search patient by ID
7. Exit the program
(b) Allow the user to select an option from the menu, perform the requested option, show the user the results, and finally show menu to the user again to let picking another option.
2. Design-Needs of your program
(a) Your program should create a struct or class called patientType to hold information about a single patient: first name (string), last name (string), patient ID (int).
(b) You also need to define an array to hold the list of patients. Each element of the array will of type struct or class patientType that you created in step 2(a) above. You can create a static array (like in Chapter 8) with a max size = 10.
(c) Your program must be a modular one: That is, printing of the menu (in step 1a above) on the screen as well as each operation in the menu should have a corresponding function. Then, the main function of your program should be mostly composed of function calls. That is, your main function should be a short function that mainly calls other functions!
(d) Sorting: For options 3 and 4 in the menu (that is sorting the patient list by last name or ID), you have to use and adapt one of the sorting algorithms in the text book: Bubble Sort (Chapter 16 , page 1019), Insertion Sort (Chapter 16, pg 1024) or Selection Sort (Chapter 8, pg 533).
(e) Searching: For option 5 and 6 (searching the patients by last name or ID), you have to use the binary search algorithm and adapt it to your program (Chapter 16, pg 1026).
3. Other Important Notes
(a) The outputs of your program should be nicely formatted. You should provide the user enough explanations to use your program comfortably.

1. If your program handles the patient list (in step 2b) and all the corresponding operations (step 2c) using a vector (Chapter 16) of struct or class patientType, you will get up to +20 points.
2. If your menu also has a working delete option as well, you will get up to a total of +10 points. You can delete a patient using last name or ID. Handling each will be an extra +5 point.
3. We studied Bubble Sort in detail in class, you are responsible to study Selection and Insertion Sort on your own for the exam. For this assignment, if you complete part 2d above (that is both the sorting options in the menu) either using Selection Sort (Chapter 8, pg 533) or Insertion Sort (Chapter 16, pg 1024) you will get an extra +5 points.
III. What to Submit:
1. Your assign4-yourName.cpp file for the program.
2. You also have to submit a README file named README-yourName.txt. Your README should include the following
a. Explain what works what does not work in your program – If your program has extra features, you can mention it too.

b. Include several test cases that you used to test the correctness of your code.

You can upload your files to this Angel drop box as a single .zip file or one by one (note that you should do one submission but you can attach multiple .cpp files to your submission!).
IV. Grading:
100 pts in total. See the Assignment rubric on how your assignment will be evaluated.
1. 90% – Your .cpp file, its content, and programs execution
2. 10% – The README file and its content
3. Extra Credit: Up to 32 points of extra credit for additional features (that is use of vector’s in the program and adding delete option).