算法---二分查找练习-1（在排序数组中查找元素的第一个和最后一个位置）

1. 题目解析

题目地址：点这里

2. 讲解算法原理

算法原理如下：

1. 首先，判断数组是否为空，如果为空，则直接返回{-1, -1}表示没有找到目标元素。

2. 初始化左指针left为0，右指针right为数组长度减1。

3. 创建一个空的vector ret，用于存储结果。

4. 查找左端点：

• 使用循环，当left小于right时执行循环。
• 计算中间元素的索引mid，使用left加上right减去left的差值的一半。
• 如果nums[mid]小于目标元素target，则说明目标元素在mid的右侧，将left更新为mid+1。
• 如果nums[mid]大于等于目标元素target，则说明目标元素在mid的左侧或者就是mid本身，将right更新为mid。

5. 判断左端点是否为目标元素：

• 如果nums[left]不等于目标元素target，则说明数组中不存在目标元素，返回{-1, -1}表示未找到。
• 否则，将left添加到ret中。

6. 重新初始化左指针left为0，右指针right为数组长度减1。

7. 查找右端点：

• 使用循环，当left小于right时执行循环。
• 计算中间元素的索引mid，使用left加上right减去left的差值的一半再加1。
• 如果nums[mid]大于目标元素target，则说明目标元素在mid的左侧，将right更新为mid-1。
• 如果nums[mid]小于等于目标元素target，则说明目标元素在mid的右侧或者就是mid本身，将left更新为mid。

8. 将right添加到ret中。

9. 返回ret，即包含目标元素左右边界的索引。

3. 编写代码

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;
        vector<int> ret;
        //查找左端点
        while(left<right)//细节
        {
            int mid=left+(right-left)/2;//细节
            if(nums[mid]<target) left=mid+1;
            else if(nums[mid]>=target) right=mid;
        }
        //判断查找值是否在数组中
        if(nums[left]!=target) return {-1,-1};
        ret.push_back(left);
        left=0,right=nums.size()-1;
        //查找右端点
        while(left<right)//细节
        {
            int mid=left+(right-left+1)/2;//细节
            if(nums[mid]>target) right=mid-1;
            else if (nums[mid]<=target) left=mid;
        }
        ret.push_back(right);
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28