CSC 160-2 Lab 8-1 Binary Search

You are going to follow instructions to write a program that can be used to demonstrate the step by step operation of the binary search algorithm. The program will display the array being searched through an array of text fields. The program will also, at each step of the demonstration, display the current values of index variables lower and upper that indicate the portion of the array currently being searched. There will also be text fields to display the mid value for the middle index, and another text field to allow the user to enter a search value.

1. Building the User Interface

Start with the following code

package lab8_1prog;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JTextField;
/**
 *
 * @author your name here
 */
public class Lab8_1Prog
{
    public static void main(String[] args) 
    {
        final int WIDTH = 5;
        // Text fields to display the array elements
        // as well the indices lower, upper, and mid.
        // There is also a text field to display the value being 
        // searched for.
        JTextField[] numberTfs = new JTextField[20];
        JTextField lowerTf = new JTextField(WIDTH),
                   midTf = new JTextField(WIDTH),
                   upperTf = new JTextField(WIDTH);
        JTextField searchValueTf = new JTextField(WIDTH);

        // Button to create a new random array to start a new search,
        // and a button to perform the next search step
        JButton newRandomButton = new JButton("New Random Array");
        JButton nextStepButton = new JButton("Search Step");


        JFrame frame = new JFrame("Binary Search");
        frame.pack();
        frame.setVisible(true);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); 
    }
}

Compile and run the program. Of course you won't see anything interesting because key functionality is missing.

2. Add an Array of text fields on the NORTH border

Create a panel with a GridLayout of 1 row and 20 columns. Create a JTextField object for each component of the array NumberTfs and add the text fields to the panel. Each text field should have a column width of 5. Add the panel to the North side of the frame. The JFrame should now look like what you see below, except it will have 20 text fields instead of 10.

3. Add a border around the top panel

We can pretty up the interface a little bit by adding some space around the panel. We will do this by adding an empty border with space of 10 pixels at the top, right, bottom, and left side of the panel.

  topPanel.setBorder(new EmptyBorder(10, 10, 10, 10));

You have to import the javax.swing.border.* classes to do this.

4. Add the 4 Text fields to the Center of the frame

Add the lower, mid, upper, and search text fields to the center of the frame. Remember that you can only put one component in the center region, so you will need to use a panel to contain these text fields. Your frame should now look like this

5. Put titled borders around the 4 text fields

It would be nice if the user had some sort of indication of the function of the 4 text fields. We want to put titled borders around each of text fields, and have our user interface look like this:

You can put a border with title "lower" around the lowerTf text field like this

lowerTf.setBorder(new TitledBorder("lower"));

5. Add the two Buttons at the bottom of the frame

Add the two buttons at the bottom of the frame so the user interface now looks like this:

6. Prepare to add listeners to the button

The listener will need to be passed the array of number text fields as well as the four text fields for lower, mid, upper, and search value.

6. Add A Listener for the two Buttons

The listener class has the following outline

class BSearchListener implements ActionListener
{
    private int [] arr;
    private int lower, mid, upper;
    
    private JTextField[] numberTfs;
    private JTextField lowerTf, midTf, upperTf, searchValueTf;
    
    public BSearchListener(JTextField[] numberTfs, JTextField lowerTf,
                           JTextField midTf, JTextField upperTf, 
                           JTextField searchValueTf)
    {
        
    }

    @Override
    // Decides which one of the two methods
    // createNewArray and doSearchStep to call
    // and calls that method.
    public void actionPerformed(ActionEvent e)
    {
        throw new UnsupportedOperationException("Not supported yet."); 
    }
    /**
      * createNewArray
      * Creates a new random array of integers,
      * the array,
      * initializes lower = 0, upper to length of array -1,
      * and initializes mid to average of lower and upper.   
      * Sets the background color of text fields to white. 
      * Displays the correct values in all the text fields
      * other than the searchValue text field.
     */
    private void createNewArray()
    {
        
    }
    /**
     * doSearchStep
     * Checks if lower > upper. If so, displays a
     * JOptionPane saying the value is not in the array
     * and returns. Otherwise,
     * Compares arr[mid] to value in searchValue
     * text field. If the value is found, doSearchStep will put
     * out a JOptionPane saying the value was found at mid and return.
    
     * If the value is not found, doSearchStep will update mid,
     * lower, and upper according to the logic of binary search.
     * doSearchStep will then update the lower, mid, and upper 
     * Text fields.  Then, doSearchStep will color all the textfields
     * to the left of lower, yellow; and will color all the textfields to
     * the right of upper, pink.
     */
    private void doSearchStep()
    {
        
    }
    
}


7. Write the actionPerformed Method

This is a very short method. It examines the ActionEvent argument to determine which of the two buttons was clicked to call the listener, and then calls one of the two methods createNewArray or doSearchStep.

8. Write the createNewArray() Method

Write the body of this method using the comments on the method, and your understanding of how binary search works. Create the requisite array and fill it with random numbers. The size of the array arr will be the same as the size of the numberTfs array. Restrict yourself to non-negative random integers less that 100.

Binary Search requires the array to be sorted.

You can do this with the sort method of the Arrays class:
Arrays.sort(arr);

9. Add an instance of BSearchListener to the newRandomButton

Add code to the main method to create an ButtonListener object and add it as a listener to the newRandomButton button. You can now run the program.

You can see an example of what your program should do in the screen shot above. Notice that the user will need to type a value into the Search text field before clicking on the next Search Step button.

We need to implement the doSearchStep() method to complete the program.

10. Write the code for the doSearchStep method

Follow the comments on this method, and, being guided by your knowledge of the Binary Search algorithm, write the body of the method.

11. Attach a Listener to the nextStepButton button

Modify the code in the main method so you create just one listener and add it to both buttons.

12. Run the Program

You can now run the program. If correct, it should work as follows. First, the user clicks the button to create a random array, and then types in a value into the search text field:

Next, the user clicks the next step button. At this point, half of the array is eliminated as having contents that are too large to include the search value.

If the user clicks again, half of the remaining array is eliminated, this time because its contents are too small to include the search value

This time, one more click to do another step finds the search value.

Due Date

Due Friday of Week 8 at midnight.