难度中等1176
给定一个按照升序排列的整数数组 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] <= 109nums是一个非递减数组-109 <= target <= 109
通过次数321,737提交次数757,933
class Solution {
public int[] searchRange(int[] nums, int target) {
int [] ans = {-1,-1};
for(int i = 0;i<nums.length;i++)
{
if(ans[0]==-1 && nums[i]==target) ans[0] = i;
if(nums[i]==target) ans[1] = i;
}
return ans;
}
}
二分查找：
class Solution {
public int[] searchRange(int[] nums, int target) {
//二分查找
int start = 0;
int end = nums.length-1;
int mid;
int [] ans = new int[2];
ans[0] = -1;
ans[1] = -1;
while(start<=end)
{
mid = (end-start)/2+start;
if(nums[mid]==target)
{
ans[0] = mid;
ans[1] = mid;
for(int i=mid;i<nums.length;i++)
{
if(nums[i]==target) ans[1] = i;
}
for(int i=mid;i>=0;i--)
{
if(nums[i]==target) ans[0] = i;
}
return ans;
}
else if(nums[mid]>target) end=mid-1;
else start = mid+1;
}
return ans;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/69171.html
