题目描述

假设一个单调递增的数组里的每个元素都是整数并且是唯一的。

请编程实现一个函数找出数组中任意一个数值等于其下标的元素。

例如，在数组 [−3,−1,1,3,5] 中，数字 3 和它的下标相等。

样例

输入：[-3, -1, 1, 3, 5]

输出：3

算法

(二分) $O(logn)$

假设第 $i$ 个数的值小于下标，由于数组单调递增且每个数唯一，所以前 $i - 1$ 个数同样是值小于下标的，那么答案肯定不在 $[0, i - 1]$ 区间内，所以根据这个性质，就可以将区间划分为两部分，一部分是数值小于下标，另一部分数值大于等于下标，我们需要二分出第一个值大于等于下标的数，即数值和下标相等的元素。

1. 二分初始区间 $[l, r]$，l = 0, r = nums.size() - 1, mid = l + r >> 1
2. 如果数值大于等于下标 nums[mid] >= mid，更新区间 r = mid
3. 如果数值小于下标 nums[mid] < mid，更新区间 l = mid + 1
4. 如果二分结束没有找到答案，返回 -1

时间复杂度

C++ 代码

class Solution {
public:
    int getNumberSameAsIndex(vector<int>& nums) {
        if (nums.empty()) return -1;

        int l = 0, r = nums.size() - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (nums[mid] >= mid) r = mid;
            else l = mid + 1;
        }

        if (l != nums[l]) return -1;
        return l;
    }
};