在Java中查找以排序的String数组中的指定String开头的第一个元素

Question

我在Java中有一个排序的String数组.我试图找到第一个以该数组中用户指定的String开头的元素.我首先考虑二进制搜索,但它找到相等的String而不是以用户指定的String开头的String.我应该如何修改二进制搜索,以便实现我想要做的？

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