Datawhale模拟面試每日打卡 day-06在排序數組中查找元素的第一個和最後一個位置

解題思路：

• 本題要求時間複雜度為O(logn)，而且題目所給的條件是一個有序數組，是以采用二分查找的思想，分别查找左右邊界，這裡需要重點注意邊界條件的設立，還有就是死循環問題的解決。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        //判斷是否為空vector
        if(nums.size()==0)return{-1,-1};
        int left = 0;
        int right = nums.size() -1;
        //尋找左邊界
        int left_index = findLeft(nums,target,left,right);
        if(left_index ==-1)return {-1,-1};
        //尋找又邊界
        int right_index = findright(nums,target,left,right);
        return {left_index,right_index};
    }
    //左邊界二分查找
    int findLeft(vector<int> nums,int target,int left,int right){
        int mid = 0;
        while(left<right){
            //确定中間值
            mid = left+(right-left)/2;
            if(nums[mid]<target)left = mid+1;//中間值所在的值小于目标值說明中間值和中間值左邊的值都不可能是左邊界值
            else if(nums[mid]==target)right = mid;//中間值所在的值等于目标值，說明中間值右邊的值都不可能是左邊界值
            else right = mid-1;//中間值所在的值大于目标值說明，中間值和中間值右邊的值都不可能是左邊界值
        }
        if(nums[left]==target)return left;
        else return -1;
    }
    //右邊界二分查找
    int findright(vector<int> nums,int target,int left,int right){
        int mid = 0;
        while(left<right){
            //防止進入死循環導緻，是以對中間值進行+1，向上取整操作，具體可以看最下面的示範
            mid = left+(right-left+1)/2;
            if(nums[mid]<target)left = mid+1;//中間值所在的值小于目标值說明中間值和中間值左邊的值都不可能是右邊界值
            else if(nums[mid]==target)left = mid;//中間值所在的值等于目标值，說明中間值左邊的值都不可能是左邊界值
            else right = mid-1;//中間值所在的值大于目标值說明，中間值和中間值右邊的值都不可能是右邊界值
        }
        //有邊界查找是建立在已經查找到左邊界的情況下，是以不需要進行判斷 nums[left]==target
        return left
    }
};
           

右邊界查找問題中的死循環問題解決方案的詳細