二進制搜索幫助：將文件讀入數組，找到特定行

Question

在文件中，每個條目將包含兩行;第一行是數字，第二行是標題。文件中的條目將按數字升序排列。

創建一個將文件讀入數組的程序。用戶然後將基於該號碼請求標題。您的程序將執行二進制搜索以查找標題。

目前，我從文件中讀取所有內容到一個arrayList中，然後將其轉換爲一個數組。

我的第一個主要問題是我的二進制搜索方法似乎沒有工作;我試圖搜索一個數字，它只是返回false。其次，即使這個設法工作，我不確定如何記錄文本文件中找到結果的哪一行。我認爲這是必要的，因爲我必須在後面輸出行。這是文本文件外觀的一個例子。

彌賽亞劇

晚間祈禱

良性的下迫害

等祈禱這是我的當前代碼

package Psalms; 

import java.io.*; 

import javax.swing.*; 

import java.util.ArrayList; 

import java.util.List; 

public class Psalms { 



public static void main(String[] args) throws IOException { 
    // Creates array list. Reads lines into it 
    List<String> psalms = new ArrayList<String>(); 
    BufferedReader readFile = new BufferedReader(new FileReader("Psalms.txt")); 
    String line; 
    while ((line = readFile.readLine()) != null) { 
     psalms.add(line); 
    } 
    readFile.close(); 

    String[] psalmArray = new String[psalms.size()]; 
    psalmArray = psalms.toArray(psalmArray); 

    //Asks user what to search for. 
    String psalmSearch = (JOptionPane.showInputDialog("What number Psalm would you like to search for?")); 
    System.out.println("Binary Search: " + psalmSearch + " " + binarySearch(
      psalmArray, 0, psalmArray.length - 1, psalmSearch)); 

} 

public static boolean binarySearch(String myArray[], int left, 
     int right, String searchForPsalm) { 
    int middle; 

    if (left > right) { 
     return false; 
    } 
    middle = (left + right)/2; 
    if (myArray[middle].equals(searchForPsalm)) { 
     return true; 
    } 
    if (searchForPsalm.compareTo(myArray[middle]) < 0) { 
     return binarySearch(myArray, left, middle - 1, 
       searchForPsalm); 
    } else { 
     return binarySearch(myArray, middle + 1, right, 
       searchForPsalm); 
    } 
} 

}

Answer 1

現在，你在做什麼是添加每行一個字符串的文件列表英寸因此，這份名單將是這樣的：

<"2", "The messianic drama", "4", "Evening prayer", "7"> 

的問題是，當你嘗試執行這個二進制搜索，你是比較一些字符串與標題，有的還帶有數字。

這裏是我推薦的方法，假設你得到的文件已經排序：

當你把它們添加到兩個不同的列表，其中包含標題之間讀取文件的線，交替和其他數字作爲整數。當您從文件中添加數字時，請確保使用Integer.parseInt（String）將其轉換爲整數。我們的想法是創建兩個列表如下：

Title List = <"The messianic drama", "evening prayer", "Prayer of the virtuous under 
persecution"> 
Tile Number List: <2,4,7> 

你看到2是如何在列表中的其他The messianic drama相同指數？

然後，當您執行二分查找查找標題編號時，如果找到要查找的編號，則只需將標題列表中的字符串返回到相同的位置即可。

如果您的標題沒有按照文件順序編號，您可能需要考慮製作一個元組String和Integer。這有點複雜，因爲您必須創建一個類並實現一個比較器，以便您可以對它們進行正確排序。

Answer 2

假設您的文件被正確驗證（即每詩數字後跟文本行），則對於現有的binarySearch方法，有2個修正需要：

. 
    . 
    middle = (left + right)/2; 
    middle += middle & 1; // to the nearest even number 
    . 
    . 
    . 
    } else { 
     return binarySearch(myArray, middle + 2, right, 
       searchForPsalm); 
    } 
} 

1）由於所有的詩數是在偶數陣列的位置，則需要確保中間被設置爲最接近的偶數偏移量。

2）對於'右側'分區，您應該跳過文本行，將其設置爲'middle + 2'。

這將確保您按照預期比較讚美詩數字。

現在，而不是返回一個布爾值，你可以返回一個字符串，如果發現顯示相關的文字，所以這裏是修改後的方法：

public static String binarySearch(String myArray[], int left, 
     int right, String searchForPsalm) { 
    int middle; 

    if (left > right) { 
     return ""; 
    } 
    middle = (left + right)/2; 
    middle += middle & 1; 
    if (myArray[middle].equals(searchForPsalm)) { 
     return myArray[middle + 1]; 
    } 
    if (searchForPsalm.compareTo(myArray[middle]) < 0) { 
     return binarySearch(myArray, left, middle - 1, 
       searchForPsalm); 
    } else { 
     return binarySearch(myArray, middle + 2, right, 
       searchForPsalm); 
    } 
} 

它會返回一個空字符串，如果沒有條目中找到。另外，如果您還需要返回'中間'值，您可以修改它以返回一個對象，比如Result，它同時具有「中間」和字符串值 - 請參閱示例：

How to return multiple values in java?