java - 在Java中的排序字符串数组中查找以指定字符串开头的第一个元素

Question

我在 Java 中有一个排序的字符串数组。我试图在该数组中找到以用户指定的字符串开头的第一个元素。一开始我以为是二分查找，但它找到的是相等的字符串，而不是以用户指定的字符串开头的字符串。我应该如何修改二分查找才能实现我想做的事情？

Answer 1

如果元素不存在，二分查找可以找到“比所需元素小的最后一个元素”(有时称为“您应该插入它的索引”)。

通过使用此功能进行二分查找，您可以找到一个元素并检查:

1. 如果它是确切的元素 - 那么它就是数组中具有该前缀的第一个元素，因为它是具有该前缀的“最小”元素，您就完成了。
2. 如果它不是同一个元素——通过增加一个——你会得到“比所需元素大的最小元素”。此元素是数组中具有此前缀的第一个元素(如果数组有前缀)。

此功能非常常见 - 例如它存在于 java 的 Arrays.binarySearch() 中.来自 javadocs:

Returns: index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key

从刚刚找到的索引，很容易找到想要的元素。

代码快照:

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]);