二進制搜索與字前綴字符串越界

我有一個程序，創建一個類字典，其中它填充字符串arrayList與命令行參數（按字母順序，所有不同長度）給出的單詞。無論如何，我需要實現二分查找，以在字典中查找前綴作爲回溯方法的一部分。當前綴長於字典中的單詞時，我遇到了問題---我試圖調整這種情況的二進制搜索，但它產生了不正確的結果。我真的不明白二進制搜索足以解決這個問題。如果我不考慮前綴長於一個單詞的問題，那麼.subString會生成字符串indexoutofbound。任何幫助將不勝感激。二進制搜索與字前綴字符串越界

public int searchPrefix(String prefixKey){ 
    int minIndex=0; 
    int maxIndex= newDictionary.size()-1; 
    return searchPrefix(prefixKey, minIndex,maxIndex); 
} 

public int searchPrefix(String prefixKey, int minIndex, int maxIndex){ 
    if(minIndex>maxIndex){ 
     return-1; 
    } 
    int midIndex=(maxIndex-minIndex)/2+minIndex; 
    if (prefixKey.length()>newDictionary.get(midIndex).length()){ 
     return searchPrefix(prefixKey, midIndex+1,maxIndex); 
    } 
    else if(newDictionary.get(midIndex).length(<prefixKey.length()&&newDictionary.get(midIndex).compareTo(prefixKey.substring(0,newDictionary.get(midIndex).length()))>0){ 
     return searchPrefix(prefixKey,minIndex,maxIndex); 
    } 
    else if(newDictionary.get(midIndex).substring(0,prefixKey.length()).compareTo(prefixKey)>0){ 
     return searchPrefix(prefixKey,minIndex,maxIndex-1); 
    } 
    else if(newDictionary.get(midIndex).length()<prefixKey.length()&&newDictionary.get(midIndex).compareTo(prefixKey.substring(0,newDictionary.get(midIndex).length()))<0){ 
     return searchPrefix(prefixKey,minIndex,maxIndex); 
    } 
    else if(newDictionary.get(midIndex).substring(0,prefixKey.length()).compareTo(prefixKey)<0){ 
     return searchPrefix(prefixKey, midIndex+1,maxIndex); 
    } 
    else 
     return midIndex; 
}

來源

2015-10-10 drt

從Collections類採取binarySearch方法和改進的根據自己的需要。

private static int binarySearch(List<String> list, String key) { 
    int low = 0; 
    int high = list.size() - 1; 
    while (low <= high) { 
     int mid = (low + high) >>> 1; 

     String midVal = list.get(mid); 

     int cmp = -1; 

     if (midVal.length() > key.length()) 
      cmp = midVal.substring(0, key.length()).compareTo(key); 
     else 
      cmp = key.substring(0, midVal.length()).compareTo(midVal) * -1; 

     if (cmp < 0) 
      low = mid + 1; 
     else if (cmp > 0) 
      high = mid - 1; 
     else 
      return mid; // key found 
    } 
    return -1; // key not found 
}

希望這會幫助你。

來源

2015-10-10 04:53:35 Saravana

我不認爲這是有用的。給定字典「abc」，「abcd」，「abcde」...「abcdefgh」，在索引2處找到鍵「abc」.OP沒有提供足夠的輸入用於任何可靠的編碼。 – laune

是的，這就像檢查包含，看字典可能有助於決定。 – Saravana

@Amy Gold你能分享字典嗎？ – Saravana

String方法compareTo處理不同長度的字符串值，因此（例如）「ABC」在「ABCD」之前，因此方法中的所有這些情況區別都不是必需的。

級聯語句的開始：

if (prefixKey.length() > newDictionary.get(midIndex).length()){ 
    return searchPrefix(prefixKey, midIndex+1,maxIndex); 
} 
else if(newDictionary.get(midIndex).length() < prefixKey.length() && ...

但是論文條件是相同的，這意味着，第二分支從未達到。

你有兩種說法：無限遞歸的結果：

return searchPrefix(prefixKey,minIndex,maxIndex);

在任何情況下遞歸調用可以用完全一樣傳遞給當前呼叫相同的參數進行。

爲什麼不能使用Arrays.binarySearch？

因爲您沒有描述過問題，所以我不能真正提出改進建議。請舉一個例子，給出一個小字典和一組預期結果的密鑰。

來源

2015-10-10 05:05:14 laune

二進制搜索與字前綴字符串越界

回答

相關問題