本文共 1308 字，大约阅读时间需要 4 分钟。

34.在排序数组中查找元素的值

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

你的算法时间复杂度必须是 O(log n) 级别。

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

二分法

• 和33一样又是O(log n) 级别的时间复杂度，所以还是考虑二分法。
• 这次二分法主要的问题是数组中有重复的与target相同的数
• 解决方法是找到target后用双指针向两边遍历直到找到不同的数或者越界。

class Solution {public:    vector
   
     searchRange(vector
    
     & nums, int target) {        if(nums.size()==0) return {-1,-1};        if(nums.size()==1 && nums[0]==target) return {0,0};        else if(nums.size()==1) return {-1,-1};        int mid=0;        int left=0;        int right=nums.size()-1;        while(left <= right){            mid=(left+right)/2;            if(nums[mid] == target){                int i=mid-1,j=mid+1;                while(i>=0){                    if(nums[i] == target){                        i--;                    }                    else{                        break;                    }                }                while(j < nums.size()){                    if(nums[j] == target){                        j++;                    }                    else{                        break;                    }                }                return {i+1,j-1};            }            else if(nums[mid] > target) right=mid-1;            else if(nums[mid] < target) left=mid+1;        }        return {-1,-1};    }};
    
   

通过时间：

转载地址：http://liemb.baihongyu.com/