是否有采用一元谓词而不是搜索值的二进制搜索算法？

Question

我有这个练习：

Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.
For example, input [3, 4, -1, 1] should give 2 and input [1, 2, 0] should give 3.
You can modify the input array in-place.

我的实现：

template <typename In_It>
int missingPositiveInt(In_It first, In_It last){
    first = std::find_if( first, last, [](int x){return x > 0;} );
    if(first == last || *first > 1)
        return 1;
    for( auto next = first; (++next != last) && ( !(*next - *first > 1) ); )
        ++first;

    return *first + 1;
}

int main(){

    std::vector<int> v{5, 2, -1, 7, 0};
    std::sort(v.begin(), v.end());
    std::cout << missingPositiveInt(v.cbegin(), v.cend()) << '\n';

    v = {2, -1, 1, 0};
    std::sort(v.begin(), v.end());
    std::cout << missingPositiveInt(v.cbegin(), v.cend()) << '\n';

    v = {5, 2, -1, 7, 0};
    std::sort(v.begin(), v.end());
    std::cout << missingPositiveInt(v.cbegin(), v.cend()) << '\n';

    v = {3, 4, -1, 1};
    std::sort(v.begin(), v.end());
    std::cout << missingPositiveInt(v.cbegin(), v.cend()) << '\n';

    v = {1, 2, 0};
    std::sort(v.begin(), v.end());
    std::cout << missingPositiveInt(v.cbegin(), v.cend()) << '\n';

    std::cout << '\n';
}

输出：

该程序工作正常，但我使用算法 std::find_if 查找序列（排序序列）中的第一个正值，并且该算法进行线性搜索。

只要输入序列已经排序，我想使用一些二进制搜索算法来加速这个过程。
我尝试使用 std::binary_search，但它需要搜索参数。我需要的是获得一个采用一元谓词并应用二进制搜索或任何其他更快的算法来找到序列中最低正值的版本，这样我就可以写：
```
auto it = binary_search(first, last, [](int x){ return x > 0; });
```

可能吗？我的代码没问题还是我需要修改它。因此，非常感谢任何建议和提示。

Answer 1

部分解决方案基于@numzero 的回答。这不处理数组中的负数或零，但您可以通过对数组进行线性预处理以预先删除它们来处理。它只是通过取反将每个索引标记为“已找到”，然后查找第一个非负值，这就是那个。尽管它是部分解决方案，但它显示了核心算法。

#include <iostream>
using namespace std;

int main() {
    
    int arr[] = {1, 4, 6, 7, 2, 7, 7, 8, 3};
    
    int arrSize = sizeof(arr)/sizeof(int);
    
    for(int i=0; i<arrSize; ++i)
    {
        int val = abs(arr[i]);
        if(val > 0 && val-1 < arrSize)
        {
            if (arr[val-1]>0)
            {
                arr[val-1] = -arr[val-1];
            }
        }
    }
    
    for(int i=0; i<arrSize; ++i)
    {
        if(arr[i] > 0)
        {
            std::cout << "Smallest is " << (i+1) << std::endl;
            return 0;
        }
    }
    
    std::cout << "Nothing found!" << std::endl;
    
    // your code goes here
    return 0;
}

Answer 2

是的，std::partition_point 完全符合您的要求。

是否有采用一元谓词而不是搜索值的二进制搜索算法？

Is there a binary search algorithm that takes a unary predicate rather than a search value?

c++

binary-search