使用二进制搜索来计算小于/大于给定数字的元素数量

6 回答

• 0

  二进制搜索算法为数组中不存在的值生成"insertion point" . 你的 startIndex 和 endIndex 会给你第一个"eligible"项目，或者它旁边的项目 . 换句话说，如果您要查找小于 6 的所有值，搜索 endpoints 将产生 5 的索引 .

  请注意，您不需要使用自己的二进制搜索算法：Java为您提供了一个实现 .

  参考：Arrays.binarySearch

  回复于 2024-05-22T11:13:56+08:00
• 2

  EDIT 问题已被编辑，现在它包含一个额外的要求，即算法应该能够快速地进行多个查询，更准确地说：整个运行时应该是 O((N + Q) * log(N)) ，其中 N 是数组的大小， Q 是查询的数量 .

  以下方法仅适用于 Q = 1 .

  ---

  我认为没有任何理由不在线性 O(N) 时间内这样做 .

  // get this from scanner
  int number = 5;
  int[] array = {6, 2, 7, 4, 1, 42};
  
  // the "algorithm"
  int numLessThan = 0;
  int numGreaterThan = 0;
  for (int i: array) {
    if (i < number) numLessThan++;
    if (i > number) numGreaterThan++;
  }
  System.out.println(
    "Num greater than: " + numGreaterThan + " " +
    "Num less than: " + numLessThan
  );
  

  输出：

  Num greater than: 3 Num less than: 3
  

  如果你坚持用流来做：

  long numLessThan = Arrays.stream(array).filter(x -> x < number).count();
  long numGreaterThan = Arrays.stream(array).filter(x -> x > number).count();
  

  即使它遍历数组两次，它仍然是 O(N) .

  回复于 2024-05-22T11:13:56+08:00
• 2

  因为你无论如何使用 Stream ，并且 map -call也不少，你无论如何都在迭代整个数组 .

  所以就这么做

  class Counters {
      AtomicInteger smaller = new AtomicInteger(0);
      AtomicInteger larger = new AtomicInteger(0);
      private final int upperLimit;
      private final int lowerLimit;
      public Counters(int up, int down) {
          upperLimit = up;
          lowerLimit = down;
      }
      public void consider(int value) {
          if (value > upperLimit) larger.incrementAndGet();
          if (value < lowerLimit) smaller.incrementAndGet();
      }
      public int getSmaller() { return smaller.get(); }
      public int getLarger() { return larger.get(); }
  }
  
  Counters c = new Counters(upper, lower);
  IntStream.of(yourValues).parallel().forEach(c::consider);
  // your output here
  System.out.printf("Smaller: %d - Larger: %d", c.getSmaller(), c.getLarger());
  

  或更通用的版本

  class MatchCounter<T> {
      AtomicInteger count = new AtomicInteger(0);
      private final Predicate<T> match;
      public MatchCounter(Predicate<T> m) { match = m; }
      public void consider(T value) {
          if (m.test(value)) { count.incrementAndGet(); }
      }
      public int getCount() { return count.get(); }
  }
  
  MatchCounter<Integer> smaller = new MatchCounter<>(i -> i < lower);
  MatchCounter<Integer> larger = new MatchCounter<>(i -> i > upper);
  Consumer<Integer> exec = smaller::consider;
  Stream.of(yourArray).parallel().forEach(exec.andThen(larger::consider));
  System.out.printf("Smaller: %d - Larger: %d", smaller.getCount(), larger.getCount());
  

  回复于 2024-05-22T11:13:56+08:00
• 1

  见Arrays，这将在这里派上用场 .

  void stats(int[] a, int sought) {
      a = Arrays.copyOf(a, a.length);
      Arrays.sort(a);
      int index = Arrays.binarySearch(a, sought);
      int smaller, larger;
      if (index < 0) {
          // Not found.
          index = ~index; // Insertion position.
          smaller = index;
          larger = index:
      } else {
          // Found.
          smaller = index;
          while (smaller > 0 && a[smaller] == sought) {
              --smaller;
          }
          while (index <= 0 && a[index] == sought) {
              ++index;
          }
      }
      larger = a.length - index;
      int equals = index - smaller;
      System.out.printf("Smaller %d, equal %d, larger %d.%n",
              smaller, equals, larger); 
  }
  

  如你所见，当找到一个元素时，回路O（N）就足够了，它小于排序O（N log N） .

  更快 - O（log N）而不是O（N）用于该部分 - 如果可以对搜索的二进制搜索 - 0.5并且寻求0.5 .

  void stats(int[] a, int sought) {
      a = Arrays.copyOf(a, a.length);
      for (int i = 0; i < a.length; ++i) {
          a[i] *= 2;
      }
      Arrays.sort(a);
      int smallerI = Arrays.binarySearch(a, 2 * sought - 1);
      int largerI = Arrays.binarySearch(a, 2 * sought + 1);
      int smaller = ~smallerI;
      int larger = a.length - ~largerI;
      int equals = ~largerI - ~smallerI;
      System.out.printf("Smaller %d, equal %d, larger %d.%n",
              smaller, equals, larger); 
  }
  

  这使用了加倍的整数，其缺点是数组值的有效域减半 .

  在您的情况下，您自己的二进制搜索算法应该选择后一种情况（不加倍），使用隐式 sought + 0.5 ，永远不会找到，寻找插入位置 .

  回复于 2024-05-22T11:13:56+08:00
• 3

  好的，所以在编辑之后你声明你想在同一个数组上运行几个查询，所以准备时间不那么重要了 .

  为此，从数组中构建red-black tree;这将为您提供一个允许在O（log N）中搜索的排序结构 .

  那么你对“较小”计数所做的就是向左移动，直到找到一个值等于或大于下限的节点;算上所有左边的孩子 . 模拟较大的（向右，找到相等或更小，向右计数） .

  如果该项目不在数组中，则无关紧要，因为您正在寻找“等于或大于”的项目，如果6不存在，但是你找到了5，你会从那里算起来 - 只有你在计数中加1 .

  回复于 2024-05-22T11:13:56+08:00
• 1

  You just have to filter and then count occurences. 例如：

  public static void main(String[] args) {
      int[] values = {5, 8, 7, 2, 4, 3, 7, 9, 1, 9};
      printCount(values, 7);
      printCount(values, 0);
      printCount(values, 100);
      printCount(values, 3);
      printCount(values, 6);
  
  }
  private static void printCount(int[] values, int value) {
      long smallerCount = Arrays.stream(values).filter(v -> v < value).count();
      long largerCount  = Arrays.stream(values).filter(v -> v > value).count();
      System.out.println(String.format("Smaller : %d, Larger: %d", smallerCount, largerCount));
  }
  

  回复于 2024-05-22T11:13:56+08:00