查找给定排序数组中不存在的最小数字 >= x

Question

我在编写修改后的二进制搜索算法时遇到困难，该算法 returns 大于或等于 X 的最小数字不存在于排序数组中。

例如，如果数组是{1,2,3,5,6}和x = 2，那么答案就是4。请指导我如何为此编写二进制搜索。我必须在 O(log n) 时间内为每个 x 回答这个问题。由于我将此数组作为输入，最初需要线性时间，因此如果需要，您可以先对数组进行某种预处理。

x 也作为输入，可能存在也可能不存在于数组中。

输入数组可能有重复元素。

我的输入数字可以在 [0,10^9] 范围内，因此首先将所有缺失值放入数组中是不可行的，因为 space 限制。

此外，您可以进行预处理，这需要 O(n) 时间，因为您将数组作为线性时间的输入。在那之后，让我们说 X 的 10^6 个查询，你必须在 O(log n) 时间内回答每个

Answer 1

如果数组中不存在 x，则 return x。

如果 x 存在，则说它位于 l 位置。另外，我们将 missing(i) 表示为 i 左侧缺失的元素数。在 1 索引数组中，这等于 A[i]-i。然后从 l 一直向右移动直到 missing(i) - missing(l) = 0。您可以为此使用修改后的二进制搜索。假设 p 是最后一个元素的位置，其中 missing(p) - missing(l) = 0 那么 A[p]+1 是第一个大于 x.

的缺失数

Answer 2

看看这个：

    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    int greaterValue(const vector<int>& elements, int x){
        int low = 0, 
            high = elements.size() -1, 
            answer = x + 1;
        
        while (low <= high) {
            int mid = (low + high) / 2;
            if (elements[mid] <= answer) {
                if (elements[mid] == answer) {
                    answer++;
                    high = elements.size() - 1;
                }
                low = mid + 1;
            }
            else {
                high = mid - 1;
            }
        }
        return answer;
    }
    
    int main() {
        vector<int> elements = { 1, 2, 3, 5, 6 };
        int x = 2;
        int result = greaterValue(elements, x);
        cout << "The element is: " << result;
        return 0;
    }

测试：

    { 1, 2, 3, 5, 6 }

结果：

    The element is: 4

时间复杂度：

    O(log(n))

Answer 3

如果我没理解错的话，你可以进行任何类型的预处理，并且只发现不同 x 的结果必须是 O(log n)。如果是这样的话，在预处理之后找到结果并不是什么大问题。 O(log n) 确实存在搜索算法。好的候选人是 std::binary_search 或 std::lower_bound。

一种非常幼稚的方法是准备一个包含所有缺失元素的向量，然后 std::lower_bound 在其上：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> input{1,2,3,5,6,10,12};
    std::vector<int> missing_elements{4,7,8,9,11};
    int x = 2;
    auto it = std::lower_bound(missing_elements.begin(),missing_elements.end(),x);
    std::cout << *it << "\n";
}

填充 missing_elements 可以在 O(1) 中完成。但是，一个missing_elements，大小为10^9量级，当然是行不通的。此外，这种方法对于像 [1,100000000] 这样的输入非常浪费（不是在时间复杂度方面，而是在运行时和内存使用方面）。

Jarod42 在评论中提出的一个想法是准备一个分段向量，然后 std::lower_bound 在其上。首先假设预处理已经完成：

#include <iostream>
#include <vector>
#include <algorithm>

int find_first_missing(const std::vector<std::pair<int,int>>& segments,int x){
    std::pair<int,int> p{x,x};
    auto it = std::lower_bound(segments.begin(),segments.end(),p,[](auto a,auto b){
        return a.second < b.second;
    });
    if (it == segments.end()) return x;
    if (it->first > x) return x;    
    return it->second+1;
}

int main() {
    std::vector<int> input{1,2,3,5,6,10,12};
    std::vector<std::pair<int,int>> segments{{1,3},{5,6},{10,10},{12,12}};
    for (int x=0; x<13;++x) std::cout << x << " -> " << find_first_missing(segments,x) << "\n";
}

Output:

0 -> 0
1 -> 4
2 -> 4
3 -> 4
4 -> 4
5 -> 7
6 -> 7
7 -> 7
8 -> 8
9 -> 9
10 -> 11
11 -> 11
12 -> 13

因为input是排序的，而segments是排序的，我们可以使用自定义比较器，只比较段的末尾。段向量也根据该比较器进行排序。对 lower_bound returns 的调用是指向 x 位于内部或 x 低于该段的段的迭代器，因此 if (it->first > x) return x; 否则我们知道 it->second+1 是下一个缺失的数字。

现在只剩下创建分段向量了：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

std::vector<std::pair<int,int>> segment(const std::vector<int>& input){
    std::vector<std::pair<int,int>> result;
    if (input.size() == 0) return result;
    
    int current_start = input[0];
    for (int i=1;i<input.size();++i){
        if (input[i-1] == input[i] || input[i-1]+1 == input[i]) continue;
        result.push_back({current_start,input[i-1]});
        current_start = input[i];        
    }
    result.push_back({current_start,input.back()});
    return result;
}

int main() {
    std::vector<int> input{1,2,3,5,6,10,12};
    std::vector<std::pair<int,int>> expected{{1,3},{5,6},{10,10},{12,12}};
    auto result = segment(input);
    for (const auto& e : result){
        std::cout << e.first << " " << e.second << "\n";
    }
    assert(expected == result);
}

查找给定排序数组中不存在的最小数字 >= x

Finding smallest number >= x not present in the given sorted array

c++

sorting

binary-search