Find First and Last Position of Element in Sorted Array - LeetCode

我会带着你远行 2021-09-30 15:06 128阅读 0赞

*  题目链接
 *  注意点
 *  解法
 *  小结

# 题目链接 #

[Find First and Last Position of Element in Sorted Array - LeetCode][]

# 注意点 #

*  `nums`可能为空
 *  时间复杂度为O(logn)

# 解法 #

**解法一：最普通的二分搜索，先找到一个target，然后向两边拓展。**

class Solution {
    public:
        int binarySearch(vector<int>& nums, int target)
        {
           int left = 0,right = nums.size()-1;
            while(left <= right)
            {
                int mid = left + (right-left)/2;
                if(nums[mid] == target) return mid;
                if(nums[mid] < target) left = mid+1;
                else right = mid-1;
            }
            return -1;
        }
        vector<int> searchRange(vector<int>& nums, int target) {
            vector<int> ret;
            int index = binarySearch(nums,target);
            int left = index,right = index;
            while(left > 0 && nums[left-1] == nums[index]) --left;
            while(right < nums.size()-1 && nums[right+1] == nums[index]) ++right;
            ret.push_back(left);
            ret.push_back(right);
            return ret;
        }
    };

![874b0eb1gy1g0arlncnmfj21690kj0tt.jpg][]

**解法二：解法一在最坏情况下时间复杂度是O(n),比如整个`nums`都是target。因此我们用两次二分搜索，第一次找到第一个等于target的数字，第二次找到最后一个等于target的数字。时间复杂度O(logn)**

class Solution {
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
            vector<int> ret;
            int left = 0,right = nums.size()-1;
            while(left <= right)
            {
                int mid = left+(right-left)/2;
                if(nums[mid] >= target) right = mid-1;
                else left = mid+1;
            }
            if(left >= 0 && left < nums.size() && nums[left] ==  target) ret.push_back(left);
            else return {-1,-1};
            left = 0;right = nums.size()-1;
            while(left <= right)
            {
                int mid = left+(right-left)/2;
                if(nums[mid] <= target) left = mid+1;
                else right = mid-1;
            }
            if(right >= 0 && right < nums.size() && nums[right] == target) ret.push_back(right);
            return ret;
        }
    };

![874b0eb1gy1g0arr560z8j217e0p7q4a.jpg][]

# 小结 #

*  [二分搜索][Link 1]变种题

转载于:https://www.cnblogs.com/multhree/p/10397258.html

[Find First and Last Position of Element in Sorted Array - LeetCode]: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
[874b0eb1gy1g0arlncnmfj21690kj0tt.jpg]: https://ws1.sinaimg.cn/large/874b0eb1gy1g0arlncnmfj21690kj0tt.jpg
[874b0eb1gy1g0arr560z8j217e0p7q4a.jpg]: https://ws1.sinaimg.cn/large/874b0eb1gy1g0arr560z8j217e0p7q4a.jpg
[Link 1]: https://www.cnblogs.com/multhree/p/10351731.html#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0