【剑指offer】数组中数值和下标相等的元素(二分查找)
程序员文章站
2024-03-22 23:22:40
...
题目描述
假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编写实现一个函数,找出数组中任意一个数值等于其下标的元素。例如,在数组{-3,-1,1,3,5}
中,数字3和它的下标相等。
思路
二分查找,时间复杂度O(log n)
代码
class Solution {
public:
int getNumberSameAsIndex(vector<int> nums){
if(nums.empty()) return 0;
int left = 0, right = nums.size()-1;
while(left <= right){
int mid = (left+right)/2;
if(nums[mid] == mid)
return mid;
else if(nums[mid] < mid)
left = mid + 1; // 右区间
else
right = mid - 1;
}
return -1;
}
};```