1.算法题目
给定一个按照升序排列的整数数组 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]
2.算法思路
算法思路：
- 暴力法-线性扫描：从头到尾遍历数组可以找到元素第一个位置，从尾到头遍历可以找到元素出现的最后一个位置；
- 二分查找：因为数组是排序的数组，所以可以用二分法查找元素的位置，通过设置标识 left来表示是在查找第一个位置还是最后一个位置。
3.算法代码
根据线性扫描算法思路编写的算法实现代码如下：
public int[] searchRange(int[] nums, int target) {
int[] targetRange = {-1, -1};
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
targetRange[0] = i;
break;
}
}
if (targetRange[0] == -1) {
return targetRange;
}
for (int j = nums.length-1; j >= 0; j--) {
if (nums[j] == target) {
targetRange[1] = j;
break;
}
}
return targetRange;
}
根据二分查找算法思路编写的算法实现代码如下：
public int[] searchRange(int[] nums, int target) {
int[] range = {-1, -1};
int leftIndex = searchIndex(nums, target, true);
if (leftIndex == nums.length || nums[leftIndex] != target) {
return range;
}
range[0] = leftIndex;
range[1] = searchIndex(nums, target, false) - 1;
return range;
}
private int searchIndex(int[] nums, int target, boolean left) {
int low = 0;
int hight = nums.length;
while (low < hight) {
int mid = (low + hight) / 2;
if (nums[mid] > target || (left && target == nums[mid])) {
hight = mid;
} else {
low = mid + 1;
}
}
return low;
}
4.总结
看题目的要求算法时间复杂度必须是 O(log n) 级别，就能很快想到要用二分法，由于需要查找目标元素第一个和最后一个位置，所以可以使用二分法查找两次元素，第一次查找第一个位置，第二次查找最后一个位置，通过加标识区分查找的是第一个还是最后一个位置。这个算法题考察的是二分法的一个改进算法。
如果你有疑问或更好的算法思路，欢迎留言交流！！！
如果感觉我的文章对您有所帮助，麻烦动动小手给个喜欢，谢谢！！！
