跟着姚桑学算法-数组中数值和下标相等的元素

题. 数组中数值和下标相等的元素

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

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

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

数据范围
数组长度 [1,100]。

样例

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

输出：3

注意: 如果不存在，则返回-1。

【题解】--- 二分法

直接进行二分法即可；

二分法 ，即一分为二的方法。通过不断地把函数的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫二分法。

它的思路在于：查找过程从数组的中间元素开始：如果中间元素正好是要查找的元素，则查找过程结束；

如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。

如果在某一步骤数组为空，则代表找不到。

复杂度分析：

时间复杂度为O(logn)。

C++代码实现：

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[l]!=l) return -1;
        else return nums[r];
    }
};