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() メソッドの実装方法に関する仕様です。問題の解決方法を学ぶには、これまでに学習したさまざまなフロー制御ステートメントを使用して、各ヒント ステートメントを段階的に実行し、結果がテストに合格するかどうかを確認することをお勧めします。

実際、今日多くのプロの開発者が働いています。実際にコード自体を書く前に、達成したいことの結果を説明するテスト ケースを書きます。テストに合格したら終了します。

指示が明確でないため、Google の「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 に答える