Java递归二分查找

Question

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

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 语句，也许还有其他一些东西，但我不知 Prop 体是什么。我知道我应该做什么，但不知道如何去做。以下是书中的一些提示，但我不确定如何实现:

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

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

Answer 1

注意:回答是因为我缺少发表评论的代表

这很令人沮丧。那么，您复制的书中的提示是关于如何实现 binarySearch() 方法的规范。我建议学习解决问题的方法是逐步执行每个提示语句，使用您目前学到的各种流程控制语句，并查看结果是否通过您的测试。

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

由于说明不明确，谷歌“java二进制搜索”为您提供了什么？像二分查找这样的计算机科学基础知识有许多示例和解释，可能对学生来说更好。

This可能有帮助。