欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【剑指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;
    }
};```

相关标签: 二分查找