力扣-34题在排序数组中查找元素的第一个和最后一个位置（C++）- 二分法+双指针

迷南。 2022-09-03 05:21 67阅读 0赞

题目链接：[https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/][https_leetcode-cn.com_problems_find-first-and-last-position-of-element-in-sorted-array]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]

class Solution {
        
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
        
            vector<int> result={
        -1,-1};
    
            int low=0,high=nums.size()-1,mid;
            bool flag=false;
    
            while(low<=high){
        
                mid=(low+high)/2;
    
                if(nums[mid]>target) high=mid-1;
                else if(nums[mid]<target) low=mid+1;
                else if(nums[mid]==target) {
        flag=true;break;}
            }
    
    
            if(flag){
        
                result[0]=result[1]=mid;//确定当前元素的区间，进而双指针法向两边外扩
    
                for(int i=mid-1;i>=0;i--){
        
                    if(nums[i]==target) result[0]=i;
                    else break;
                }
                
                for(int i=mid+1;i<nums.size();i++){
        
                    if(nums[i]==target) result[1]=i;
                    else break;
                }
    
            }
    
            return result;
        }
    };

[https_leetcode-cn.com_problems_find-first-and-last-position-of-element-in-sorted-array]: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20220829/5c4a2b109b624d11b3d0d8e59e61b2d4.png