34、在排序数组中查找元素的第一个和最后一个位置
【34、在排序数组中查找元素的第一个和最后一个位置】给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
解要求时间复杂度为O(log n)，提示使用二分查找。所以使用二分查找先查找出数组中有没有目标元素，如果有则使用flag记录元素的位置，然后从flag向左向右遍历，找到目标元素的起始位置的结束位置。注意在使用二分查找是i+1==j需要break掉。
public static int[] searchRange(int[] nums, int target) {
int res[] = new int[] {-1,-1};
int len = nums.length;
if(0==len||targetnums[len-1])
return res;
if(1==len&&target==nums[0])
return new int[] {0,0};
int i = 0, j = len,flag = -1;
while(inums[mid])
i = mid;
else
j = mid;
}
if(-1==flag)
return res;
int left = flag,right=flag;
while(left>=0&&nums[left]==target)
left--;
while(right 推荐阅读
- 你到家了吗
- 一个人的碎碎念
- 野营记-第五章|野营记-第五章 讨伐梦魇兽
- Shell-Bash变量与运算符
- 闲杂“细雨”
- 杜月笙的口才
- 赢在人生六项精进二阶Day3复盘
- 清明，是追思、是传承、是感恩。
- 祖母走了
- 樱花雨