给定排序列表，如何创建在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](包括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是剩余部分的大小。