使用带有比较器的二进制搜索来查找第一次出现

Question

我正在尝试对算法和数据结构 class 进行自动完成赋值，在赋值中它要求您创建一个 class 来查找键的第一次出现和最后一次出现一把钥匙。

我运行遇到的问题是我不明白如何在这个问题中实现比较器，我在设置二进制搜索时遇到了问题，因为当我尝试比较 key < a[mid] 它的说二元运算符的操作数错误，因为我使用的是对象，我知道比较器在这里生效，但是如何？

// Return a[] 中第一个关键字的索引等于搜索关键字，如果没有这样的关键字则为 -1。使用二进制搜索

    public static <Key>int firstIndexOf(Key[] a, Key key, Comparator<Key> comparator) {

        int low = 0;
        int high = a.length - 1;
        int result = -1;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (key == a[mid]) {
                result = mid;
                high = mid - 1;
            }else if (key < a[mid]) { //**<--- throws bad operand type for binary operator**         
            high = mid - 1;   // key is probable to lie before mid element
            }else {
           low = mid +1;  // key is probable to lie after mid 
           }
        }
            return result;
}

我应该传递的有问题的比较器是这样的，它使用字符串中的子字符串方法查找 rValue 以查看两个对象之间的前缀顺序是否匹配。同样，我不知道我是否一开始就这样做了，但这不是问题，问题是我将如何在另一个 class

中实现它

// 按字典顺序比较术语，但只使用每个查询的前 r 个字符。

 public static class prefixOrder implements Comparator<Term> 
    { public prefixOrder(int r){
      rValue = r;
    }

    @Override
    public int compare(Term v, Term w){
    return  v.queryItem.substring(rValue).compareTo(w.queryItem.substring(rValue));
    }

    }

link 到作业 https://www.cs.princeton.edu/courses/archive/fall14/cos226/assignments/autocomplete.html

Answer 1

你不能像在Java中那样写key < a[mid]，而是调用比较器的compare方法：

if (comparator.compare(key, a[mid]) < 0) ...

它是这样工作的：比较方法 return positive/zero/negative 值取决于比较如何结束。我记得是这样的:

a OP b --> comparator.compare(a, b) OP 0

其中 OP 是 >、>=、<、<=、==、!=

中的任何一个

此外，您可能希望将方法声明更改为：

public static <Key>int firstIndexOf(Key[] a, Key key, Comparator<? super Key> comparator)

例如，您可以使用动物比较器从狗数组中选择最小值，其中 Dog extends Animal。（阅读有关 wildcards 的更多信息。）

使用带有比较器的二进制搜索来查找第一次出现

using Binary search with a comparator to find first occurance

java

binary-search

comparator