查找以Java中的排序字符串數組中的指定字符串開頭的第一個元素

Question

我在Java中有一個有序的字符串數組。我試圖找到第一個以該用戶指定的字符串開頭的元素。我首先想到了二分搜索，但它發現相同的字符串不是以用戶指定的字符串開頭的字符串。我應該如何修改二進制搜索，以便我可以實現我想要做的事情？

Answer 1

如果元素不存在（有時被稱爲「您應該插入它的索引」），二進制搜索可以找到「最後元素小於所需元素」。

這樣做的二進制搜索使用這一功能，你可以找到一個元素，並檢查：

1. 如果是準確的元素 - 那麼以這個前綴數組中的第一個元素，因爲它是「最小「的元素，並且你已經完成了。
2. 如果它不是相同的元素 - 通過增加一個 - 你會得到「最小的元素大於所需的元素」。該元素是數組中第一個具有此前綴的元素（如果該數組有一個）。

此功能非常常見 - 例如它存在於java的Arrays.binarySearch()中。從javadocs：

返回：搜索鍵的索引，如果它包含在數組中;否則， （ - （插入點） - 1）。插入點被定義爲點 在將鍵插入到數組： 第一個元素除密鑰

從剛發現的指數越大的指數，它是很容易找到的需要的元件。

代碼卡：

String[] arr = { "aa" , "bb","c", "cc" , "ccc", "cccc", "ddD" }; 
int idx = Arrays.binarySearch(arr, "c"); 
if (idx < 0) 
    System.out.println(arr[-1 * idx - 1]); 
else System.out.println(arr[idx]);