[34. Find First and Last Position of Element in Sorted Array]

(https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/)

二分法

• 此题不像之前的二分查找题目，若只用一个二分查找很混乱，因此我推荐用两个二分法更为得当，分别去找满足条件的左右边界

• 寻找target的左右边界，存在三种情况：

  • target不满足数组内大小范围
  • target满足数组大小范围，但数组内不存在target
  • target既满足数组大小范围，且数组内存在target

• 接下来即可运用两个二分法（左闭右闭）去找满足条件的左右边界：

  • 左边界：若数组中存在target的话，那么最后一轮循环，left和right都必将指向target值，又因为 if( nums[middle] >= target ) right = middle - 1，right肯定会指向最左边的target。最后，right会继续向左移动，因此left是左边界的答案

    while(left <= right)
    {
        int middle = left + ( ( right - left ) >> 1 );
    
        if( nums[middle] >= target ) right = middle - 1;
        else left = middle + 1;
    }
    
    int L = left;
    

  • 右边界：与左边界同理

    while(left <= right)
    {
        int middle = left + ( ( right - left ) >> 1 );
    
        if( nums[middle] <= target ) left = middle + 1;
        else right = middle - 1;
    }
    
    int R = right;
    

  • 全部实现：

    class Solution {
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
            if( nums.size() == 0 ) return { -1, -1 };
    
            int left = 0, right = nums.size() - 1;
    
            while(left <= right)
            {
                int middle = left + ( ( right - left ) >> 1 );
    
                if( nums[middle] >= target ) right = middle - 1;
                else left = middle + 1;
            }
    
            //左边界
            int L = left;
            
            left = 0, right = nums.size() - 1;
    
            while(left <= right)
            {
                int middle = left + ( ( right - left ) >> 1 );
    
                if( nums[middle] <= target ) left = middle + 1;
                else right = middle - 1;
            }
    
            //右边界
            int R = right;
    
            //处理三种情况
            if( L > R ) return {-1, -1};
    
            return {L, R};
        }
    };
    

  • 时间复杂度：O(log_n)

    空间复杂度：O(1)