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

题目链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
题目如下:
力扣-34题 在排序数组中查找元素的第一个和最后一个位置(C++)- 二分法

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;
    }
};
上一篇:12.STC15W408AS单片机比较器


下一篇:MySQL之索引