是否存在接收一元谓词而非指定搜索值的二分查找算法？

一、现有代码的核心问题 #

你的实现首先不符合题目的线性时间要求：你调用了std::sort对数组排序，该算法的时间复杂度为O(nlogn)，已经超出了题目要求的O(n)上限，即使后续查找步骤优化到O(logn)，整体复杂度依然不达标。

二、二分查找需求的实现方案 #

你要在已升序排序的序列中找第一个正值的需求完全可以实现，C++标准库已经提供了对应的二分查找工具：

1. 最简便的方案是用std::lower_bound，直接查找第一个大于等于1的元素即可：

   auto first_positive = std::lower_bound(first, last, 1);
   

   该函数内部就是二分实现，时间复杂度O(logn)，完全可以替换你现在用的线性查找std::find_if。
2. 如果你需要接收一元谓词的版本，可以使用std::partition_point，这个函数专门用于在已经按谓词分区的有序序列中，查找第一个不满足谓词的元素，正好匹配你的场景：

   // 谓词返回true的元素（<=0的元素）都在序列左侧，返回第一个不满足谓词的元素（即第一个>0的元素）
   auto first_positive = std::partition_point(first, last, [](int x) { return x <= 0; });
   

三、符合题目要求的优化建议 #

如果要满足题目O(n)时间、O(1)空间的要求，建议用原地哈希的标准解法，不需要排序：
核心思路是把值为i的正整数放到数组下标为i-1的位置，遍历完成后再扫描一遍数组，第一个下标pos对应的元素不等于pos+1时，pos+1就是第一个缺失的正整数。
参考实现如下：

int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        // 把当前元素放到它应该在的位置
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            swap(nums[i], nums[nums[i] - 1]);
        }
    }
    // 扫描找第一个缺失的
    for (int i = 0; i < n; ++i) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return n + 1;
}

内容的提问来源于stack exchange，提问作者Itachi Uchiwa