给定排序列表如何创建不会在 O(log(N)) 时间内落入特定范围的整数列表？

Question

我有一个排序的整数数组列表（无重复项）：

{1,2,4,5,8,12,15, 21,23,26,30,32,35,37,40,42,45,48,51,54}

假设给定范围是 [21-38]（含），必须从整数输出列表中排除。

那么输出应该包含不包含上述范围的整数列表。

{1,2,4,5,8,12,15,40,42,45,48,51,54}

我需要在 O(log(N)) 时间内完成。

目前我能想到的办法是：

Approach1:
1) Find lower bound index using binary search in O(logN)
2) Find higher bound index using binary search in O(logN)
3) Then loop over the input list and add the integers to new list by 
considering above lower and higher bound index. But this third step takes O(n).

Approach2:

I also feel that the above approach of using binary search is not 
 great as we can directly iterate over original list to remove the 
  integers falling under the range without using binary search.

我们有更好的方法吗？

Answer 1

通过根据余数和删除的大小估计更好的选项，可以针对更好的情况优化元素的删除：

static List<Integer> removeFrom(List<Integer> sorted, int sv, int ev) {
    int i1 = Collections.binarySearch(sorted, sv);
    int i2 = Collections.binarySearch(sorted, ev);
    int from, to;
    if (i1 < i2) {
        from = i1;
        to = i2;
    } else {
        from = i2;
        to = i1;
    }
    System.out.printf("Removing values %d..%d%n", sv, ev);
    int size = sorted.size();
    int removeLength = to - from + 1;
    int remainLength = size - removeLength;
    if (removeLength < remainLength) {
        System.out.printf("Removing range: [%d, %d]%n", from, to);
        sorted.removeAll(sorted.subList(from, to + 1));
        return sorted;
    } else {
        List<Integer> result = new ArrayList<>();
        if (from > 0) {
            System.out.printf("Keeping head: [%d, %d]%n", 0, from);
            result.addAll(sorted.subList(0, from));
        }
        if (to < size - 1) {
            System.out.printf("Keeping tail: [%d, %d]%n", to, size);
            result.addAll(sorted.subList(to + 1, size));
        }
        return result;
    }
}

测试：

int[][] tests = {
    {1, 3},
    {7, 10},
    {3, 6},
    {2, 10},
    {1, 9},
    {2, 9}
};
for (int[] test : tests) {
    List<Integer> sorted = IntStream.rangeClosed(1, 10).boxed().collect(Collectors.toList());
    System.out.println("result: " + removeFrom(sorted, test[0], test[1]) + "\n====\n");
}

输出

Removing values 1..3
Removing range: [0, 2]
result: [4, 5, 6, 7, 8, 9, 10]
====

Removing values 7..10
Removing range: [6, 9]
result: [1, 2, 3, 4, 5, 6]
====

Removing values 3..6
Removing range: [2, 5]
result: [1, 2, 7, 8, 9, 10]
====

Removing values 2..10
Keeping head: [0, 1]
result: [1]
====

Removing values 1..9
Keeping tail: [8, 10]
result: [10]
====

Removing values 2..9
Keeping head: [0, 1]
Keeping tail: [8, 10]
result: [1, 10]
====

因此，在最佳情况下，复杂度为 O(M)，其中 M 是剩余部分的大小。

给定排序列表如何创建不会在 O(log(N)) 时间内落入特定范围的整数列表？

Given sorted list how to create list of integers that wont fall in certain range in O(log(N)) time?

java

algorithm

binary-search

data-structures