题目描述

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

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

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

样例

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

输出：3

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

算法

(二分) $O(log^n)$

1. 由于该序列是单调的，要找到下标和元素值相等的元素，即nums[i] == i
2. 可以发现如果取该序列的中点，一定有一边存在下标等于值的元素，一边不存在下标等于值的元素，即满足二段性，可以用二分
3. 每次取中点，判断中点值和下标的大小关系来确定是左区间还是右区间
4. 如果最后取到的值不等于自己的下标，则认为不存在，返回 -1 即可

Java 代码

class Solution {
    public int getNumberSameAsIndex(int[] nums) {
        int n = nums.length;

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

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

        return r;
    }
}