1

我正在使用递归编写二进制搜索算法，但我只是不知道如何开始。这是我到目前为止所拥有的：

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)
    {

    }
}

在“public int binarcySearch()”部分的底部是我卡住的地方。我想我需要一些带有返回的 if 语句，也许还有其他一些东西，但我不知道具体是什么。我知道我应该做什么，但不知道怎么做。以下是书中的一些提示，我不确定如何实施：

  • 如果您的 lowIndex 输入大于您的 highIndex，则返回 -1，因为您已经完成了对数组的搜索并且找不到目标值。
  • 使用二分搜索讨论中描述的公式计算整数 midIndex 值：midIndex = lowIndex + (highIndex - lowIndex) / 2。
  • 检查 midIndex 处目标数组的值。如果它与你的 targetValue 匹配，你就完成了，所以返回你的 midIndex 作为最终结果！
  • 如果未找到您的 targetValue，则需要递归调用 binarySearch()，修改 lowIndex 和 highIndex 参数以删除不包含目标的数组部分。
    • 如果中间值太高，请在递归函数调用中使用现有的 lowIndex 和等于 midIndex -1 的 highIndex。
    • 如果中间值太低，请使用等于 midIndex + 1 的 lowIndex 和递归函数调用中的现有 highIndex
    • 您的递归 binarySearch() 调用将返回目标值的索引，如果未找到则返回 -1，因此您可以直接从父 binarySearch() 代码返回该结果。

请记住，我是一个非常早期的初学者，婴儿程序员，而我正在上的 DIY 课程在解释事情方面很糟糕。所以请简单明了。谢谢你。

4

2 回答 2

4

注意：回答是因为我缺乏评论代表

这很令人沮丧。好吧，您复制的书中的提示是关于如何实现 binarySearch() 方法的规范。我建议学习如何解决问题的方法是一步一步地使用每个提示语句，使用您迄今为止学到的各种流控制语句，并查看结果是否通过了您的测试。

事实上，这就是今天有多少专业开发人员在工作。在我们实际编写代码之前，我们编写测试用例来描述我们想要完成的结果，因为我们知道它会失败。当它通过我们的测试时，我们就完成了。

由于说明不清楚，谷歌搜索“java二进制搜索”为您带来了什么？像二进制搜索这样的计算机科学基础知识有许多可能更适合学生的示例和解释。

这可能会有所帮助。

于 2013-01-05T00:07:09.757 回答
2

这是您的代码：

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);
}
于 2013-01-05T00:07:04.653 回答