java - 使用比较器进行二分搜索

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 长度之间，我也不知道如何实现二进制搜索方法。据我所知，为了让仿函数工作，我需要将一个 Ladder 对象作为 x 传递，但是我该如何规定我要搜索的长度？ Ladder 类有一个 .length() 方法。

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

Answer 1

通过破解 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 来实现它函数类似于内置函数，因为如果未找到元素，它将返回负数插入索引。所以我们可以搜索区间末尾的元素，如果找到则返回它，如果没有找到只需检查插入索引处的项目是否在区间内，然后返回。这样算法将返回区间中的最后一个元素。

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() .这使得实现像这样的甜蜜功能成为可能(lambda 使它变得漂亮):

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按属性订购元素。简单的任务，简单的解决方案。不幸的是，我不知道标准库或第三方中有这样的功能。但它们是可以实现的。

Java 8 中的一个工作示例:

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