数组中数值和下标相等的元素-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

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

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

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

**样例**
```
输入：[-3, -1, 1, 3, 5]

输出：3
```

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

### 解法
二分法查找。
- 当前元素等于对应的下标，直接返回该下标；
- 当前元素大于该下标，在左边查找；
- 当前元素小于该下标，在右边查找。

```java
/**
 * @author bingo
 * @since 2018/12/10
 */

class Solution {
    /**
     * 找出单调递增数组中数值和下标相等的元素
     *
     * @param nums 数组
     * @return 数值与下标相等的元素
     */
    public int getNumberSameAsIndex(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0, end = nums.length - 1;
        while (start <= end) {
            int mid = start + ((end - start) >> 1);
            if (nums[mid] == mid) {
                return mid;
            }
            if (nums[mid] < mid) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return -1;
    }
}
```

### 测试用例
1. 功能测试（数组中包含或者不包含数值和下标相等的元素）；
2. 边界值测试（数组中只有一个数字；数值和下标相等的元素位于数组的开头或者结尾）；
3. 特殊输入测试（表示数组的指针为空指针）。

该分类下的相关小册推荐：

算法面试通关 50 讲

编程之道-算法面试(上)

业务开发实用算法精讲

数据结构与算法(上)

数据结构与算法之美

编程之道-算法面试(下)

数据结构与算法(下)