每天一道算法题【蓝桥杯】【在排序数组中查找元素的第一个位置和最后一个位置】

思路

本题为查找左边界和右边界的标准模型

查找左边界

int left = 0, right = nums.size() - 1, mid = 0; //查找左边界
while (left < right)
{
mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1;
else right = mid;
}

查找右边界

int left = 0, right = nums.size() - 1, mid = 0;
while (left < right)
{
mid = left + (right - left + 1) / 2;
if (nums[mid] <= target) left = mid; //查找右边界
else right = mid - 1;
}

#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
using namespace std;
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, mid = 0; //查找左边界
        vector<int> ret;
        while (left < right)
        {
            mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        ret.push_back(left);
        right = nums.size() - 1, mid = 0;
        while (left < right)
        {
            mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target) left = mid;    //查找右边界
            else right = mid - 1;
        }
        ret.push_back(right);//插入到ret表中
        if (nums[right] == target) return ret;
        else return{ -1,-1 };
    }
};