题目连接：AcWing 69. 数组中数值和下标相等的元素

一、题解

题目大意：

一个单调递增序列，有一些数是和下标匹配的，找出任意一个该数！

思路：

很明显，还是二分，关键点，二分的核心：需要找到二段性是啥！

从目标答案该数向左向右分析，可以得到：

  • 该数左边，每个数都比下标要小
  • 该数右边，每个数都比下标要大或相等

因此可以通过二分找到第二段第一个满足条件的即可，即第一个下标和数值匹配的数即可！

**时间复杂度： **O(logn)

**空间复杂度： **O(1)

二、AC代码

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int getNumberSameAsIndex(vector<int>& nums) {
        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(nums[r] == r) return r;
        return -1;
    }
};