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

题目：

​ 假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实现一个函数，找出数组中任意一个数值等于其下标的元素。例如，在数组 {-3,-1,1,3,5} 中，数字3和它的下标相等。

分析：

1. 方法一：

   从头到尾依次扫描数组中的数字，并逐一检验数字是不是和下标相等。时间复杂度为O(n)。

2. 方法二：

   ​ 由于数组是单调递增排序的，因此我们可以尝试二分查找算法来进行优化。假设我们某一步抵达数组中的第i个数字。如果我们很幸运，该数字的值刚好也是i，那么我们就找到了一个数字和其下标相等。

   ​ 当数字的值和下标不相等的时候，假设数字的值为m。先考虑m大于 i 的情形，即数字的值大于它的下标。由于数组中的所有数字都唯一并且单调递增，那么对于任意大于0的k，位于下标i+k的数字的值大于或等于m+k。另外，因为m>i，所以m+k>i+k。因此，位于下标i+k的数字的值一定大于它的下标。这意味着如果第 i 个数字的值大于i，那么它的右边的数字都大于对应的下标，我们都可以忽略。下一轮查找只需要从它左边的数字中查找即可。

   ​ 数字的值m小于它的下标i的情形和上面类似。它左边的所有数字的值都小于对应的下标，也可以忽略。

代码：

基于方法二

class NumberSameSolution {

    private static int getSameNumberAsIndex(int[] data, int length) {
        if (null == data || length <= 0) {
            return -1;
        }
        int left = 0;
        int right = length -1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (data[mid] == mid) {
                return mid;
            } else if (data[mid] > mid) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] data = {-3, -1, 1, 3, 5, 7};
        System.out.println(getSameNumberAsIndex(data, data.length));
    }
}