如何确定一个给定的单词是否介于另外两个单词之间？

Question

为了简单起见，假设我有两组单词，按字母顺序排列。一组以“土豆蔻”开头，以“甜瓜”结尾，另一组以“甜瓜”开头，以“斑马”结尾。“瓜子”这个词出现在两组中。

如果我要输入一个单词，说“香蕉”，那么确定它应该属于哪一组单词的好方法(和效率)是什么？注意:这不是一个关于“香蕉”这个词是否已经存在于一组中的问题，而是一个关于如何确定哪个词应该存在于其中的问题。

如果有人知道算法的话，那就太好了。如果他们能用Java提供一些版本，那就更好了！

编辑:也应该指出，虽然我的例子只有两个集，我希望算法与n集一起工作。

Answer 1

两组的：

如果word是你的话(例如"banana")：

int cmp = word.compareTo("melon");
if (cmp < 0) {
  // it belongs to the first set
} else if (cmp > 0) {
  // it belongs to the second set
} else {
  // the word is "melon"
}

n 集的：

将分词按字母顺序排列成ArrayList<String> (称为dividers)：

ArrayList<String> dividers = new ArrayList<String>();
//... populate `dividers` ...
Collections.sort(dividers);

现在您可以使用Collections.binarySearch()来确定哪个词是属于哪个词的：

int pos = Collections.binarySearch(dividers, word);
if (pos >= 0) {
  // the word is the divider between sets `pos` and `pos+1`
} else {
  int num = -(pos + 1);
  // the word belong to set number `num`
}

(在这里，集合从零开始编号。)

Answer 2

假设你有n集。按排序顺序构造“分区”单词的列表。

那么它所属的集合就是：

List<String> partitions = Arrays.asList("melon", "strawberry");
int setIndex = -(Collections.binarySearch(partitions, "banana")) - 1;

这是因为如果Collections.binarySearch找不到列表中的键，它会返回插入位置(-1)。如果它可能与其中一个分区词发生冲突，那么您应该首先检查结果是否为负值。

编辑

我编辑删除了对“书端”值("aardvark“和"zebra")的要求，因为它们实际上只是复杂的事情。

Answer 3

只要检查第一个字母，看看它是否介于(集合1的第一个字母)和(集合1的最后一个元素的第一个字母)之间。如果它等于前两个字母，那么移到第二个字母。如果它不适合在这组移动到下一组。这是BigO(n*m)，其中n是集合的数目，m是输入单词中的字母数。不算太糟。