Java recursive binary search

Question

I'm writing a binary search algorithm using recursion and I just don't know how to start. Here's what I have so far:

import javax.swing.*;

import java.awt.*;
import java.awt.event.*;

public class BinarySearch implements ActionListener
{

    public static void main(String[] args)
    {

        new BinarySearch();
    }


    private JSpinner searchSpinner;
    private JButton searchButton;
    private JList   searchList;


    Integer[] myNumbers = {1, 3, 5, 6, 8, 9, 10, 12, 14, 15};


    public BinarySearch()
    {
        JFrame myFrame = new JFrame();       // create the JFrame window
        myFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);


        JPanel mainPanel = (JPanel)myFrame.getContentPane();
        mainPanel.setLayout(new BoxLayout(mainPanel,BoxLayout.Y_AXIS));
        mainPanel.setBorder(BorderFactory.createEmptyBorder(10,10,10,10));


        searchSpinner = new JSpinner(new SpinnerNumberModel(5,0,99,1));


        searchButton = new JButton("Search");
        searchButton.addActionListener(this);
        searchButton.setAlignmentX(Component.CENTER_ALIGNMENT);


        searchList = new JList(myNumbers);
        searchList.setFixedCellWidth(50);
        searchList.setVisibleRowCount(myNumbers.length);


        JLabel label = new JLabel("Target Value");
        label.setAlignmentX(Component.CENTER_ALIGNMENT);


        mainPanel.add(label);
        mainPanel.add(searchSpinner);
        mainPanel.add(Box.createRigidArea(new Dimension(0,5)));
        mainPanel.add(searchButton);
        mainPanel.add(Box.createRigidArea(new Dimension(0,5)));
        mainPanel.add(searchList);


        myFrame.pack();
        myFrame.setVisible(true);
    }


    public void actionPerformed(ActionEvent event)
    {
        Object control = event.getSource();
        if (control == searchButton)
        {

            searchList.clearSelection();


            int targetValue = (Integer)searchSpinner.getValue();


            int index = binarySearch(myNumbers,targetValue,0,myNumbers.length-1);


            if (index >= 0)
            {

                searchList.setSelectedIndex(index);  
            }
            else
            {

                JOptionPane.showMessageDialog(null, "Number " + targetValue + " not found!");
            }
        }
    }


    public int binarySearch(Integer[] targetArray, int targetValue, int lowIndex, int highIndex)
    {

    }
}

At the bottom under the "public int binarcySearch()" section is where I am stuck. I think I'll need a few if statements with returns and maybe some other things, but I don't know exactly what. I know what I'm supposed to do, but not how to do it. Here are some hints from the book which I'm not sure how to implement:

If your lowIndex input is greater than your highIndex, then return -1 because you have finished searching the array and cannot find the target value.
Calculate an integer midIndex value using the formula described in the binary search discussion: midIndex = lowIndex + (highIndex - lowIndex) / 2.
Check the value of the target array at the midIndex. If it matches your targetValue, you are done, so return your midIndex as the final result!
If your targetValue was not found, then you need to recursively call binarySearch(), modifying the lowIndex and highIndex parameters to remove parts of the array that don’t contain the target.
- If the middle value too high, use the existing lowIndex and a highIndex equal to midIndex -1 in your recursive function call.
- If the middle value too low, use a lowIndex equal to midIndex + 1 and the existing highIndex in your recursive function call
- Your recursive binarySearch() call will return the index of the target value or -1 if not found, so you can return that result directly from the parent binarySearch() code.

Please keep in mind that I am a very early, beginner, baby programmer and the DIY class I'm taking sucks at explaining things. So please be simple and clear. Thank you.

Brett Bonner · Accepted Answer · 2013-01-05 00:12:39Z

4

note: answering because I lack the rep to comment

That's frustrating. Well, the hints from the book that you copied are specifications on how to implement the binarySearch() method. How I suggest learning how to solve the problem is taking each hint statement step-by-step, using the various flow control statements you've learned so far, and seeing if the results pass your tests.

In fact, that's how many professional developers work today. We write test cases that describe the outcome of what we want to accomplish before we actually write the code itself, knowing it will fail. We finish when it passes our tests.

As the instructions are not clear, what has Googling "java binary search" yielded for you? Something as fundamental to computer science as binary search has many examples and explanations that are possibly better for the student.

This may help.

edited Jan 5, 2013 at 0:12

answered Jan 5, 2013 at 0:07

Brett Bonner

4251 gold badge4 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

The Professor Over a year ago

I have several programs on my computer which keep me from visiting basically any site but the ones my parents allow. Basically my email address some military sites and this one. So I haven't been able to Google or otherwise search anything. Otherwise I definitely would have

The Professor Over a year ago

Oh and the link was VERY helpful. Thanks a bunch!

agim · Accepted Answer · 2013-01-05 00:07:04Z

2

Here is your code:

public int binarySearch(Integer[] targetArray, int targetValue, int lowIndex, int highIndex)
{
    if (lowIndex > highIndex) return -1;
    int midIndex = lowIndex + (highIndex - lowIndex) / 2;
    if (targetArray[midIndex] == targetValue) return midIndex;


    if (targetArray[midIndex] > targetValue)
       return binarySearch(targetArray, targetValue, lowIndex, midIndex-1);
    else
       return binarySearch(targetArray, targetValue, midIndex+1, highIndex);
}

answered Jan 5, 2013 at 0:07

agim

1,84113 silver badges19 bronze badges

4 Comments

The Professor Over a year ago

Thanks for the code. I modified it just a bit for readability, but I basically just copy/pasted. Only reason I didn't select your answer as the "winner" was because I saw LaughNowbutWe'llBeInCharge 's answer first, plus it also helped me understand WHY I should use what you put. Thanks.

agim Over a year ago

You are welcome. Nevertheless you should try to code it yourself one more time. It was actually a translation English->Java :-)

Colleen Over a year ago

@agim just giving him the answer kind of defeats the purpose of him learning it, doesn't it?

agim Over a year ago

Yes and no. If he does not have an idea how to start, than it's better for him to have an example and to learn through code reading.

Collectives™ on Stack Overflow

Java recursive binary search

2 Answers 2

2 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related