力扣34. 在排序数组中查找元素的第一个和最后一个位置（经典二分）

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

原题链接34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

本题的关键是找到target在nums数组中的起始位置，很明显要用二分法，但是二分的细节很容易搞错搞混。

下面介绍如何使用二分找到target在nums数组中的起始位置，换句话说，找到一个位置index，使得nums[index]>=target;

初始区间[left,right];left=0,right=n-1;求出二分中点mid=(left+right)/2;

对于mid位置，若nums[mid]<target,执行left=mid+1;否则right=mid-1;

需要对这句话进行解释：nums[mid]<target的含义是mid位置及左侧的所有元素都比target小，这时执行left=mid+1，就可以确保left左侧（不包括left）的所有元素都比target小。那么二分到循环结束时，既然left左侧（不包括left）的所有元素都比target小，从left开始，[left,n-1]的所有元素都满足>=target;

以[5,7,7,8,8,10]为例

1.[left=0,right=5],mid=2;

nums[mid]=7<target=8;

即[5,7,7]区域内所有元素都小于target=8,让left=mid+1=3;

2.[left=3,right=5],mid=4;

nums[mid]=8>=target;

让right=mid-1=3;

3.[left=3,right=3];mid=3;

nums[mid]=8>=target;

right=mid-1=2;

退出循环

此时left=3，确保了[0,left)区域所有元素小于target，那么[left,n-1]区域的元素自然大于等于target，而left也是题目要求的起始位置

由于该题可能找不到，需要对nums[left]这个点进行合法性判断，以及判断nums[left]是否等于target

至于另一个边界，可以直线遍历，不过推荐的方式是再次利用如上算法

我们如今已经找到了起始位置start，是满足nums[start]>=target的第一个点，我们是根据nums[start-1]<target原理找到的；寻找位置end也可利用nums[end+1]>target的性质，我们去寻找target+1在nums数组中的起始位置,减一即为end

class Solution {
public:
    int lower_bound(const vector<int>&nums,int target){//寻找第一个满足>=target的位置
        int n=nums.size();
        int left=0,right=n-1;
        while(left<=right){
            int mid=(right-left)/2+left;//防止溢出的取中点方式
            if(nums[mid]<target) left=mid+1;//参照讲解
            else right=mid-1;
        }
        return left;//返回的是left
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        int start=lower_bound(nums,target);
        if(start>=nums.size()||nums[start]!=target) return{-1,-1};//检查start位置是否越界且等于target
        int end=lower_bound(nums,target+1)-1;//end位置的找法
        return {start,end};
    }
};

我们的lower_bound函数的实现即为寻找有序数组中>=target的第一个位置，依照此函数，另外三种要求也可以满足

寻找>target的第一个位置，调用lower_bound(nums,target+1)

寻找<target的第一个位置，即lower_bound(nums,target)-1

寻找<=target的第一个位置，即lower_bound(nums,target+1)-1

原文地址：https://blog.csdn.net/ouliten/article/details/145119376

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！