在Java中的字符串數組的遞歸二進制搜索

我已經創建了一個字符串數組的二進制搜索，該數組應該有兩個參數，一個字查找和它正在掃描的數組。我一直在尋找我的代碼幾天，嘗試不同的事情來弄清楚該做什麼，但到目前爲止我還沒有能夠使代碼工作。我得到一個NullPointerException或ArrayIndexOutOfBoundsException。這是我到目前爲止。在Java中的字符串數組的遞歸二進制搜索

public int recSearch(String[] words, String wordToFind)throws ItemNotFoundException { 
    int start = 0; 
    int end = words.length - 1; 
    int mid = (start + end) /2; 
    if(end < start) { 
     return -1; 
    } else if (words[mid].equals(wordToFind)) { 
     incrementCount(); 
     return mid; 
    } else if(words[mid].compareTo(wordToFind) < 0) { 
     String[] split = new String[mid - 1]; 
     for(int i = 0; i < mid; i++) { 
      split[i] = words[i]; 
     } 
     return recSearch(split,wordToFind); 
    } else if(words[mid].compareTo(wordToFind) > 0) { 
     String[] split = new String[mid - 1]; 
     for(int i = 0; i < mid -1; i++) { 
      split[i] = words[i]; 
     } 
     return recSearch(split,wordToFind); 
    } 
    return -1; 
    // throw new ItemNotFoundException(); 
}

來源

2015-05-26 Shan Solo

我要求只是要確定 - 你傳遞排序數組上面的功能呢？ – pnadczuk

你將大多得到1或2作爲結果。你的兩個回報陳述是錯誤的。 'return recSearch（split，wordToFind）;'應該由'return recSearch（split，wordToFind）+ start替換'' – talex

是的，它是一個排序數組。 –

爲了實現你可以使用Collections類搜索使用binary search元素的二進制搜索。只要您可以使用

Collections.binarySearch(List,Object)

這裏尋找你更換

`int index= Collections.binarySearch(Arrays.toString(words),` "search_key");

來源

2015-05-26 10:27:19 Kartheek

該操作沒有要求開箱即用的解決方案，因此這不能回答問題。 – John

你在這部分代碼錯誤編碼它的整個方法：

else if(words[mid].compareTo(wordToFind) < 0){ 
    String[] split = new String[mid - 1]; 
    for(int i = 0; i < mid; i++){ 
     split[i] = words[i]; 
    } 
    return recSearch(split,wordToFind); 
} 
else if(words[mid].compareTo(wordToFind) > 0) 
{ 
    String[] split = new String[mid - 1]; 
    for(int i = 0; i < mid -1; i++){ 
     split[i] = words[i]; 
    } 
    return recSearch(split,wordToFind); 
}

在第一else if數組的大小應爲mid，以適應從0到mid-1的值。在第二個else if，你會填寫的是words[i+ mid+1] in words[i]。

來源

2015-05-26 10:29:22 shruti1810

當我調整它的時候，我得到的每個輸出都是-1，因爲結束<開始 –

在分割數組時出現錯誤。我在下面更正了它。請比較一下代碼，你就會明白髮生了什麼事情錯（添加輸出有助於在這種情況下很多）

public int recSearch(String[] words, String wordToFind) throws ItemNotFoundException { 
    int start = 0; 
    int end = words.length; 
    int mid = end/2; 

    if(end < start){ 
     return -1; 
    } else if(wordToFind.equals(words[mid])) { 
     incrementCount(); 
     return mid; 
    } else if(wordToFind.compareTo(words[mid]) < 0) { 
     String[] split = new String[mid]; 
     for(int i = 0; i < mid; i++){ 
      split[i] = words[i]; 
     } 
     return recSearch(split,wordToFind); 
    } else { 
     String[] split = new String[end - mid - 1]; 

     for(int i = 0; i < end - mid - 1; i++){ 
      split[i] = words[mid + i + 1]; 
     } 
     return recSearch(split, wordToFind); 
    } 
}

來源

2015-05-26 10:59:27 pnadczuk

我仍然得到一個ArrayOutOfBoundsException。 –

請爲我提供一個示例數組，我將嘗試查看問題的位置;-) – pnadczuk

在Java中的字符串數組的遞歸二進制搜索

回答

相關問題