java - 排序数组中最右最小元素的索引

Question

我有一个大的排序数组，我想快速找到最右边最小元素的索引。 O(logn)

例如

INDEX: 0 1 2 3 4 5 6 7 8 9 10 11 12
VALUE: 5 5 5 5 5 5 5 5 6 8  9  9 10 ......... N

The answer is 7

我的观点是二分查找，但我有疑问

Answer 1

由于输入已排序，二分查找将在O(log n)中找到解决方案。

对于那些认为时间复杂度为O(n)的人来说，因为他们认为必须进行线性搜索才能找到边界，但你并没有考虑清楚。

为了找到边界，在找到目标值的索引时不要停止二分搜索。您继续执行二分搜索，直到查看相邻索引。

为了说明(我将把编码作为练习留给感兴趣的各方):

INDEX: 0 1 2 3 4 5 6 7 8 9 10 11 12
VALUE: 5 5 5 5 5 5 5 5 6 8  9  9 10

在索引 0 处查找最小值，即 5。现在搜索 5 直到找到边界，即直到找到左侧值和右侧值更高的相邻索引:

INDEX: 0 1 2 3 4 5 6 7 8 9 10 11 12
VALUE: 5 5 5 5 5 5 5 5 6 8  9  9 10
       |-----------|--------------|  Found 5, so search right
                   |-----|--------|  Found 8, so search left
                   |-|---|           Found 5, so search right
                     |-|-|           Found 6, so search left
                     |-|             Adjacent, so search complete

在索引 7 和 8 之间找到边界，因此最小值的最后一个索引是:7

这可以推广到查找任何目标数字的第一个/最后一个索引，或者查找小于目标数字的最后一个索引，或大于目标数字的第一个索引，无论目标数字是否确实存在于输入中。

<小时/>

更新

因为我喜欢NavigableSet的关系搜索操作和 NavigableMap ，我认为实现 ceiling()、floor()< 的 Arrays.binarySearch(int[] a, int key) 等效方法可能会很有趣、higher() 和 lower()，以及 first() 和 last() > get() 的变体。

为了只实现一次主要的二分搜索逻辑，我决定使用函数接口(interface)/lambda 表达式来处理比较逻辑。克隆代码或使用 boolean 可能会表现得更好，但到底是什么，我只是在玩乐趣。

因此，以下是 int[] 的 6 种二分搜索方法，以及具有主要搜索逻辑的 private 方法:

/**
 * Returns the least index in this array with value strictly equal to the given key,
 * or {@code -1} if there is no such key.
 */
public static int binaryFirst(int[] a, int key) {
    int idx = binaryCeiling(a, key);
    return (idx < 0 || a[idx] != key ? -1 : idx);
}

/**
 * Returns the greatest index in this array with value strictly equal to the given key,
 * or {@code -1} if there is no such key.
 */
public static int binaryLast(int[] a, int key) {
    int idx = binaryFloor(a, key);
    return (idx < 0 || a[idx] != key ? -1 : idx);
}

/**
 * Returns the greatest index in this array with value strictly less than the given key,
 * or {@code -1} if there is no such key.
 */
public static int binaryLower(int[] a, int key) {
    return binarySearch(a, x -> Integer.compare(x, key) < 0);
}

/**
 * Returns the greatest index in this array with value less than or equal to the given key,
 * or {@code -1} if there is no such key.
 */
public static int binaryFloor(int[] a, int key) {
    return binarySearch(a, x -> Integer.compare(x, key) <= 0);
}

/**
 * Returns the least index in this array with value greater than or equal to the given key,
 * or {@code -1} if there is no such key.
 */
public static int binaryCeiling(int[] a, int key) {
    int idx = binaryLower(a, key) + 1;
    return (idx == a.length ? -1 : idx);
}

/**
 * Returns the least index in this array with value strictly greater than the given key,
 * or {@code -1} if there is no such key.
 */
public static int binaryHigher(int[] a, int key) {
    int idx = binaryFloor(a, key) + 1;
    return (idx == a.length ? -1 : idx);
}

private static int minComp = Integer.MAX_VALUE; // For stats
private static int maxComp = Integer.MIN_VALUE; // For stats
private static int countComp = 0;               // For stats
private static int countSearch = 0;             // For stats

private static int binarySearch(int[] a, IntPredicate searchRight) {
    if (a.length == 0)
        return -1;
    int comp = 0; // For stats
    int first = 0, last = a.length - 1;
    while (first + 1 < last) {
        int mid = (first + last) / 2;
        comp++; // For stats
        if (searchRight.test(a[mid]))
            first = mid;
        else
            last = mid;
    }
    int result;
    if (first == last || first == 0) {
        comp++; // For stats
        result = (searchRight.test(a[first]) ? first : first - 1);
    } else if (last == a.length - 1) {
        comp++; // For stats
        result = (searchRight.test(a[last]) ? last : last - 1);
    } else {
        result = first;
    }
    minComp = Math.min(minComp, comp); // For stats
    maxComp = Math.max(maxComp, comp); // For stats
    countComp += comp;                 // For stats
    countSearch++;                     // For stats
    return result;
}

由于有些人似乎难以接受复杂性为O(log n)，因此我在主要搜索逻辑中添加了统计信息收集。

这里是测试代码，执行 9 个值的 36 次测试 (n=9)。空输入的搜索不统计。

public static void main(String[] args) {
    System.out.println("  =      =      <      <=    >=      >");
    System.out.println("First  Last   Lower  Floor Ceiling Higher  Input");
    test();
    test(1,1,1,1,1,9,9,9,9,9);
    test(1,1,1,5,5,5,9,9,9,9);
    test(1,1,1,1,1,1,1,1,1,1);
    test(5,5,5,5,5,5,5,5,5,5);
    test(9,9,9,9,9,9,9,9,9,9);
    test(0,1,2,3,4,5,6,7,8,9);
    System.out.printf("%nStats: min=%d, max=%d, avg=%s%n",
                      minComp, maxComp, countComp / (double) countSearch);
}
private static void test(int... a) {
    System.out.printf("%3d%7d%7d%7d%7d%7d     %s%n",
                      binaryFirst(a, 5), binaryLast(a, 5), binaryLower(a, 5),
                      binaryFloor(a, 5), binaryCeiling(a, 5), binaryHigher(a, 5),
                      Arrays.toString(a));
}

输出，搜索值 5

  =      =      <      <=    >=      >
First  Last   Lower  Floor Ceiling Higher  Input
 -1     -1     -1     -1     -1     -1     []
 -1     -1      4      4      5      5     [1, 1, 1, 1, 1, 9, 9, 9, 9, 9]
  3      5      2      5      3      6     [1, 1, 1, 5, 5, 5, 9, 9, 9, 9]
 -1     -1      9      9     -1     -1     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  0      9     -1      9      0     -1     [5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
 -1     -1     -1     -1      0      0     [9, 9, 9, 9, 9, 9, 9, 9, 9, 9]
  5      5      4      5      5      6     [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Stats: min=3, max=5, avg=3.75

可以看出，执行的平均搜索 3.75 比较 (log2(9) = 3.169925)，最坏情况下的 5 比较执行一次搜索。

我还做了 4 个不同的数组，每组 10000 个值，总共 24 次搜索:

Stats: min=14, max=15, avg=14.375

再次，比较搜索 10000 个值的平均值 14.375 (log2(10000) = 13.287712)。

我认为这充分证明了我对搜索复杂度 O(log n) 的断言。

<小时/>

对于问题的完整解决方案:

public static int indexOfMostRightSmallest(int[] a) {
    return binaryLast(a, a[0]);
}
public static void main(String[] args) {
    int[] a = { 5, 5, 5, 5, 5, 5, 5, 5, 6, 8, 9, 9, 10 };
    System.out.println(indexOfMostRightSmallest(a));
}

输出

7

Stats: min=4, max=4, avg=4.0