COSC 208Programming Assignment 2Due date: 04/15/09

In this assignment you will write a program using recursive binary search, preferably in Java. In You will have to write a BinarySearchfunction that uses recursion to search a given array for a given element. This function will return the index of where the item is found. If the item is not in the array, it will return the index where it was supposed to have been.

Your program will first prompt the user for the size of the array as follows:

Enter the number of elements you want to generate for the array:

Your program will read in the number entered by the user into a variable called arrSize. You will then dynamically allocate memory for the array with size arrSize. If you don’t know how to dynamically allocate memory then always use a fixed array size of 20. However, you will lose 5 pts for using fixed size arrays. Don’t use any of the built in data structures such as ArrayList, LinkedList, HashMap, Queue etc. Use plain and simple arrays.

Then you will prompt the user to enter integers that will be inserted into your array. The integers should be inserted into the array in sorted order using binary search. After the array is filled with numbers,print the numbers on the screen. Notice that the numbers are supposed to be sorted when printed out.

Then you will prompt the user for the search item which should be an integer. This item will then be searched in the array using binary search. If the item is found, you will print the location of the item in the array. If the item is not found, print “Item not found”.

Notice that, each time you insert an integer into the array,you have to use your BinarySearch function to keep the array sorted. Regardless of whether the item is already there or not the BinarySearch function is supposed to return the index. You can insert the new item at this index position. Of course when you are inserting in the middle of the array, you have to make room for the new element by shifting everything from that point on to the right by one position.

Use the Print Screen function of your computer to show the output of a working program. This is how you can do it:

  1. Run your program from the command prompt.
  2. Press Alt+Print Screen. That means press the Print Screen button on your keyboard while holding the Alt button. This will copy a screenshot of the command prompt window.
  3. Open up a word document and paste. This will paste the screenshot on the document.
  4. I want to see the sample output from at least 3 testcases with different array sizes as given below. If all four runs don’t fit in one window, then use multiple screen shots to paste them onto your output document.

Testcase 1:

Array size = 10

Integer input for inserting = 91, 81, 71, 61, 51, 41, 31, 21, 11, 01

Testcase 2:

Array size: 15

Integer input: 8, 1, 15, 2, 14, 3, 13, 4, 12, 4, 11, 6, 10, 7, 9

Testcase 3:

Array size: 20

Integer input: 10, 11, 1, 3, 4, 5, 6, 20, 19, 18, 15, 16, 14, 12, 2, 7, 9, 8, 13, 17

  1. Finally, print this document along with your source code to bring to class. Also submit the source code and the output document using black board.