题目描述

blablabla

样例

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

输出：3

算法1

(二分) $O(logn)$

在y总的直播中，我提出了这样一个问题，就是if里面什么时候加等号，什么时候不加，回答看题意。这里的题意是找到下标等于值的数字，所有值唯一，那么有性质：左边 < target < 右边。
而y总的二分的模板是两个，一个是找到左边最后一个小于等于目标值的数，另一个是找到右边第一个大于等于目标值的数。那么可以得出左边界的代码，注意两种代码皆可，灵活运用。当然，最后我们得到的是一个可能值，这个值不一定对，所以还需要再判断一下。

C++ 代码

class Solution {
public:
    int getNumberSameAsIndex(vector<int>& nums) {
        int n = nums.size() - 1;
        int l = 0, r = n;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= mid) l = mid;
            else r = mid - 1;
        }
        if (nums[l] != l) return -1;
        else return nums[l];
    }
};