我不可能理解所描述的字符串搜索方法.什么是uFFFF？

Question

我正在阅读有关在排序的字符串数组中搜索(范围)字符串的内容.

它说:

如果要查找以"h"开头的所有字符串,可以对字符串"h"和"h\uFFFF"运行二进制搜索.这给出了以"h"开头的所有键的频带的所有索引.请注意,二进制搜索可以返回索引所在的索引,即使它实际上不在数组中也是如此.

我对这一段不明白.

h\uFFFF它是如何帮助/用于二进制搜索的,并且最后的句子也意味着即使这个搜索也有问题？

有什么帮助可以理解这里的内容吗？

Answer 1

\ uFFFF是在16位"字母表"中排序最后的"字符",即在任何有效的字母,字符或特殊符号之后.

当您对已排序数组中的字符串进行二进制搜索时,您会找到可以插入该字符串的位置.当您有多个相同的字符串时,您将获得一个位于第一个字符串之前的位置.当您在字符串后追加"字母表的最后一个字母"时,插入点将位于最后一个相同的字符串之后,因此在排序的数组中为您提供一系列相同的字符串.

想象一下:假设您不允许Z在您的文字中使用字母.现在你有一个排序的字符串数组:

0   1   2   3   4   5   6
aab abb abc abc abd bcx bdy

如果你搜索abc,二进制搜索告诉你可以插入它的第一个地方,即2.如果你搜索abcZ,那么二进制搜索将返回4,因为abcZ在字母顺序之后abc.这可以让您知道字符串占用2(包含)和4(不包括)之间的范围abc.如果两个搜索都返回相同的数字,则表示该字符串不在数组中.

在你引用的段落中,\uFFFF扮演了我的例子中"禁止字母Z"的角色.

Answer 2

\uFFFF是 Java 中可能的最大字符。由于字符串已排序，因此搜索h将找到范围的开头，而搜索h\uFFFF将找到结尾（此处假设为 unicode 字符串），因为第二个字符不能大于\uFFFF。即使它不能完全匹配字符串，搜索也会返回目标所在位置的索引，即使它并不真正存在。

更新：\uFFFF如果您正在使用 32 位块U+10FFFF（无论 Java 中是什么），则它是 16 位块中最大可能的可排序 unicode 字符。我个人从未在 Java 中使用过 32 位 unicode 块。请参阅5.2.0 规范的第 16.7 节。

U+FFFF 和 U+10FFFF。这两个非字符代码点具有与特定 Unicode 编码形式的最大代码单元值相关联的属性。在 UTF-16 中， U+FFFF 与最大 16 位代码单元值 FFFF 相关联。U+10FFFF 与最大的合法 UTF-32 32 位代码单元值 10FFFF 相关联。此属性将这两个非字符代码点呈现为可用于内部目的的哨兵。例如，它们可用于指示列表的结尾，表示索引中保证高于任何有效字符值的值，等等