给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
示例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
Java解法
思路：
- 跟昨天的类型很相似，就数组结构有变化，采用相同的二分查找来进行操作
- 这里要注意命中时前后的延伸问题，OK~
package sj.shimmer.algorithm.ten_3;
/**
* Created by SJ on 2021/2/15.
*/
class D22 {
public static void main(String[] args) {
int[] result1 = searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8);
int[] result2 = searchRange(new int[]{5,7,7,8,8,10},6);
int[] result3 = searchRange(new int[]{},0);
int[] result4 = searchRange(new int[]{2,2},2);
System.out.println(result1[0]+","+result1[1]);
System.out.println(result2[0]+","+result2[1]);
System.out.println(result3[0]+","+result3[1]);
System.out.println(result4[0]+","+result4[1]);
}
public static int[] searchRange(int[] nums, int target) {
int[] result = new int[]{-1,-1};
if (nums != null&&nums.length!=0) {
int length = nums.length;
int start = 0;
int end = length-1;
while (start<=end) {
int mid = (start+end)/2;
if (nums[mid]==target) {
//求左边界
result[0] = mid;
result[1] = mid;
for (int i = mid-1; i >= 0; i--) {
if (nums[i] ==target) {
result[0] = i;
}else {
break;
}
}
//求右边界
for (int i = mid+1; i < length; i++) {
if (nums[i] ==target) {
result[1] = i;
}else {
break;
}
}
return result;
} else if (nums[mid] < target) {
start = mid+1;
}else {
end = mid-1;
}
}
}
return result;
}
}
image
官方解
-
二分查找
主要思想一致，但查找目标有较小的差异，相比较而言，时间效率差不多，空间上稍微好一点
核心思路：
- 要找的就是数组中「第一个等于target 的位置」（记为 leftIdx）和「第一个大于 target 的位置减一」（记为 rightIdx）
- 复用方法导致了这里有些理解麻烦，但核心都是查找某个具体有限定的位置，相比较我的先命中再查边界在重复数据较多时更有优势
public int[] searchRange(int[] nums, int target) { int leftIdx = binarySearch(nums, target, true); int rightIdx = binarySearch(nums, target, false) - 1; if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) { return new int[]{leftIdx, rightIdx}; } return new int[]{-1, -1}; } public int binarySearch(int[] nums, int target, boolean lower) { int left = 0, right = nums.length - 1, ans = nums.length; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] > target || (lower && nums[mid] >= target)) { right = mid - 1; ans = mid; } else { left = mid + 1; } } return ans; }image时间复杂度： O(log n)
空间复杂度：O(1)
