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（）」部分底部是我卡住的地方。我想我會需要一些有回報的陳述或者其他一些東西，但我不知道具體是什麼。我知道我應該做什麼，但不知道如何去做。以下是這本書的一些提示這我不知道如何實現：

• 如果您lowIndex輸入比你的更大highIndex，則返回-1，因爲你已經完成搜索陣列，並不能找到目標值。
• 計算使用二進制搜索討論中所描述的式的整數midIndex值： midIndex = lowIndex +（highIndex - lowIndex）/ 2。
• 檢查在midIndex目標數組的值。如果它匹配你的targetValue，你就完成了，所以返回midIndex作爲最終結果！
• 如果未找到targetValue，則需要遞歸調用binarySearch（），修改lowIndex和highIndex參數以刪除不包含目標的數組部分。
  • 如果中間值太高，請在遞歸函數調用中使用現有的lowIndex和等於midIndex -1的highIndex。
  • 如果中間值太低，使用lowIndex等於midIndex + 1，並在您的遞歸函數調用
  • 你遞歸的binarySearch（）調用現有highIndex將返回目標值的指標或-1，如果未找到，所以你可以直接從父母binarySearch（）代碼返回結果。

請記住，我是一個非常早期的，初學者，嬰兒程序員和DIY類我正在吸的解釋的事情。所以請簡單明瞭。謝謝。

Answer 1

注：回答，因爲我缺乏代表發表意見

這是令人沮喪的。那麼，您複製的書中的提示是關於如何實現binarySearch（）方法的說明。我如何建議學習如何解決這個問題是逐步採用每個提示語句，使用迄今爲止學到的各種流控制語句，並查看結果是否通過了您的測試。

事實上，這就是今天有多少專業開發者工作。我們編寫測試用例，描述在我們實際編寫代碼之前我們想要完成的結果，並知道它會失敗。我們通過測試後就完成了。

由於說明並不清楚，谷歌搜索「java二進制搜索」有什麼用嗎？對於計算機科學來說，二進制搜索是最基本的東西，它有很多可能對學生更好的例子和解釋。

This可能會有所幫助。

Answer 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); 
}