题目描述
假设一个单调递增的数组里的每个元素都是整数并且是唯一的。
请编程实现一个函数找出数组中任意一个数值等于其下标的元素。
例如，在数组 [−3,−1,1,3,5] 中，数字 3 和它的下标相等。
数据范围
数组长度 [1,100]。
样例
输入：[-3, -1, 1, 3, 5] 输出：3 • 1 • 2 • 3
注意:如果不存在，则返回-1。
方法一：二分查找 O(logn)
因为数组中至少有一个数是其值等于其所在下标的，且该数组是递增的，所以可以以第一个数值等于其下标的数为分界线，其左边所有数的数值都一定小于其下标，而其右边所有数都一定大于等于其下标。
特殊情况： 如果不满足上述条件，则说明该数组中没有出现一个数值等于下标的数，直接返回 -1 即可。
因此，我们可以通过上面的划分条件进行二分，找到第一个数值等于下标的那个元素，如果没有则返回 -1 。
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 l; return -1; } };
欢迎大家在评论区交流~
