使用比较器进行二分查找

Question

我正在努力让它发挥作用。我需要编写一个将与 binarySearch 算法一起使用的仿函数，以找到长度在 12 到 15 个单位之间的阶梯。

这是二进制搜索：

public static <AnyType> int binarySearch(GenericSimpleArrayList<AnyType> a, AnyType x, Comparator<? super AnyType> cmp) {
    int low = 0;
    int high = a.size() - 1;
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (cmp.compare(a.get(mid), x) < 0) {
            low = mid + 1;
        } else if (cmp.compare(a.get(mid), x) > 0) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return NOT_FOUND; // NOT_FOUND = -1
}

下面是我的仿函数：

public class FindLadder implements Comparator<Ladder>{

  @Override
  public int compare(Ladder lhs, Ladder rhs) {
    return 0;
}

}

现在很明显，仿函数目前不会做任何事情，我不知道在仿函数中放什么来确定阶梯是否落在 x 和 x 长度之间，我也不知道如何实现 binarySearch 方法。据我所知，为了让仿函数工作，我需要将一个 Ladder 对象作为 x 传递，但是我该如何规定我要搜索的长度？阶梯 class 有一个 .length() 方法。

数组按从短到长的顺序排序。我根本无法更改 binarySearch 代码。我只能实现一个可以满足我需要的仿函数。

Answer 1

试试这个：

public class FindLadder implements Comparator<Ladder>{
  @Override
  public int compare(Ladder lhs, Ladder rhs) {
    if(lhs.length() < rhs.length() && lhs.length() > 12) // Suppose rhs.length() is 15
    {
        return 0;
    }
    if(lhs.length() < 12) {
        return -1;
    }
    else {
        return 1;
    }
  }
}

用 x = 15 调用 binarySearch()。喜欢 LibraryComparator.binarySearch(l, new Ladder(15), new FindLadder());

我硬编码了 12。没有别的办法了。

Answer 2

你显然 want/need 实现了你自己的二分查找，但无论如何让我参考内置方法。

来自 Collections.binarySearch(List, T, Comparator) 的 javadoc:

Returns the index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size() if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

这里的关键是插入点，或者换句话说，returned索引指向第一个>=搜索值的元素，或者size() 如果不存在这样的元素。没有 NOT_FOUND return 值。

因为您想要一个介于 12 和 15 之间的值，请搜索 12，然后验证您是否找到了一个值并且该值 <= 15 .

Answer 3

黑客的简短版本Collections.binarySearch

The framework has built-in binary search and generic List<T> interface, you should use them.

内置的 binarySearch 函数始终将主元元素作为第二个参数提供给比较器。这是未记录的行为，但我们可以利用它，使用以下比较器：

public static class FindLadderInterval implements Comparator<Ladder> {
  public final int min, max;
  public FindLadderInterval(int min, int max) {
    this.min = min;
    this.max = max;
  }
  @Override
  public int compare(Ladder lhs, Ladder rhs) {
    // ignore rhs
    int length = lhs.length();
    return length < this.min ? -1 : length > this.max ? 1 : 0;
  }
}

那你可以这样用:

int index = Collections.binarySearch(list, null, new FindLadderInterval(12, 15));

工作示例：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Main2 {

  public static class Ladder {
    private final int _length;

    public Ladder(int length) {
      this._length = length;
    }

    public int length() {
      return this._length;
    }

    @Override
    public String toString() {
      return "Ladder(" + this._length + ")";
    }
  }

  public static class FindLadderInterval implements Comparator<Ladder> {
    public final int min, max;

    public FindLadderInterval(int min, int max) {
      this.min = min;
      this.max = max;
    }

    @Override
    public int compare(Ladder lhs, Ladder rhs) {
      // ignore rhs
      int length = lhs.length();
      return length < this.min ? -1 : length > this.max ? 1 : 0;
    }
  }

  public static void main(String[] args) {
    List<Ladder> list = new ArrayList<Ladder>();

    list.add(new Ladder(1));
    list.add(new Ladder(2));
    list.add(new Ladder(6));
    list.add(new Ladder(13));
    list.add(new Ladder(17));
    list.add(new Ladder(21));

    int index = Collections.binarySearch(list, null,
        new FindLadderInterval(12, 15));
    System.out.println("index: " + index);
    System.out.println("ladder: " + list.get(index));
  }
}

使用适当算法的长版本

您在区间中查找元素的任务不是简单的二分查找，但我们可以使用类似于内置函数的 binarySearch 函数来实现它，因为 returns如果未找到元素，则 插入索引 为负数。所以我们可以搜索区间末尾的元素，如果找到则 return 它，如果没有找到只需检查插入索引处的项目是否在区间内，并且 return那。这样算法将 return 间隔中的最后一个元素。

public static <T, R extends Comparable<? super R>> int intervalBinarySearchBy(
    List<T> list, R min, R max, Function<? super T, ? extends R> selector) {
  int idx = binarySearchBy(list, max, selector);
  if (idx >= 0) return idx;
  // Collections.binarySearch returns the insertion index binary
  // negated if the element was not found
  idx = ~idx;
  return (idx < list.size()
    && min.compareTo(selector.apply(list.get(idx))) <= 0) ? idx : -1;
}

要使用内置 Collections.binarySearch 或您的函数，您需要提供一个 代表性元素 ，这在例如您按长度。要查找长度为 15 的字符串，您必须提供长度为 15 的字符串。这就是为什么我更喜欢 python 样式排序的原因，它使用 键函数 或 选择器。基本上，您不需要比较，而是映射到可比较的值。例如从 String 到 Integer 的映射，如 s -> s.length()。这使得实现像这样的甜蜜功能成为可能（lambdas 让它变得漂亮）：

List<Person> list = getPersons();
Person youngest = minBy(list, p -> p.getAge());
Person tallest = maxBy(list, p -> p.getHeight());
Person person42 = findBy(list, 42, p -> p.getAge());
sortBy(list, p -> p.getAge());

看，不需要 Comparator 就可以通过属性订购商品。简单的任务，简单的解决方案。不幸的是，我不知道标准库或第三方中有这样的功能。但它们是可以实现的。

Java8 中的工作示例：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.function.Function;

public class Main {

  public static class Collections2 {

    /**
     * Mimics Collections.binarySearch
     * 
     * @param list
     * @param pivotKey
     * @param selector
     * @return
     */
    public static <T, R extends Comparable<? super R>> int binarySearchBy(
        List<T> list, R pivotKey,
        Function<? super T, ? extends R> selector) {
      int low = 0;
      int high = list.size() - 1;
      while (low <= high) {
        int mid = (low + high) >>> 1;
        int ord = selector.apply(list.get(mid)).compareTo(pivotKey);
        if (ord < 0) {
          low = mid + 1;
        } else if (ord > 0) {
          high = mid - 1;
        } else {
          return mid;
        }
      }
      return ~high; // bitwise negated insertion point /* -(a+1) == ~a */
    }

    /**
     * Finds the index of the last element in the interval, or returns -1 if
     * no such element was found.
     * 
     * @param list
     * @param min
     * @param max
     * @param selector
     * @return
     */
    public static <T, R extends Comparable<? super R>> int intervalBinarySearchBy(
        List<T> list, R min, R max, Function<? super T, ? extends R> selector) {
      int idx = binarySearchBy(list, max, selector);
      if (idx >= 0) return idx;
      // Collections.binarySearch returns the insertion index binary
      // negated if the element was not found
      idx = ~idx;
      return (idx < list.size()
        && min.compareTo(selector.apply(list.get(idx))) <= 0) ? idx : -1;
    }

    public static <T, R extends Comparable<? super R> > Comparator<T> comparatorBy(
        Function<? super T, ? extends R> selector) {
      return (a, b) -> selector.apply(a).compareTo(selector.apply(b));
    }
  }

  public static Function<Ladder, Integer> LENGTH_OF = a -> a.length();

  public static class Ladder {
    private final int _length;

    public Ladder(int length) {
      this._length = length;
    }

    public int length() {
      return this._length;
    }

    @Override
    public String toString() {
      return "Ladder(" + this._length + ")";
    }
  }

  public static void main(String[] args) {
    List<Ladder> list = new ArrayList<Ladder>();
    list.add(new Ladder(5));
    list.add(new Ladder(9));
    list.add(new Ladder(14));
    list.add(new Ladder(7));
    list.add(new Ladder(22));
    list.add(new Ladder(23));
    list.add(new Ladder(11));
    list.add(new Ladder(9));

    Collections.sort(list, Collections2.comparatorBy(LENGTH_OF));

    int i = 0;
    for (Ladder s : list) {
      System.out.println("" + (i++) + ": " + s);
    }

    int foundIdx = Collections2.intervalBinarySearchBy(list, 12, 15,
        LENGTH_OF);
    System.out.println("Index: " + foundIdx);
    System.out.println(list.get(foundIdx));
  }
}

Answer 4

确保二进制搜索算法的前提条件：

项目必须提前按升序存储。
您必须提供具有要查找的功能的项目。

那就试试这个

public int compare(Ladder lhs, Ladder rhs) {
    boolean isLhsInRange = lhs.length() >= 12 && lhs.length() <= 15;
    boolean isRhsInRange = rhs.length() >= 12 && rhs.length() <= 15;
    if(isLhsInRange && isRhsInRange) return 0;
    else return lhs.length() - rhs.length();
}

使用比较器进行二分查找

Binary Search using Comparator

java

binary-search

functor

comparator

黑客的简短版本Collections.binarySearch

使用适当算法的长版本