本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
本题来自 LeetCode：34. 在排序数组中查找元素的第一个和最后一个位置[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]
题目分析
由于题目要求时间复杂度为
O(log n)，因此不能通过线性遍历的方式来解答。需要通知分治的方式来进行剪枝。和 的
分治法解法类似。
二分法（递归）
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] result = new int[2];
result[0] = -1;
result[1] = -1;
binarySearch(nums, target, 0, nums.length - 1, result);
return result;
}
public void binarySearch(int[] nums, int target, int left, int right, int[] result) {
if(left right) {
return;
}
int mid = (left + right) 1;
if(nums[mid] target) {
// 右半部分继续搜索
binarySearch(nums, target, mid + 1, right, result);
} else if(nums[mid] target) {
// 左半部分继续搜索
binarySearch(nums, target, left, mid - 1, result);
} else {
// 左右部分均有
// 则直接从当前位置，查找最左边的目标值
int first = mid;
while(first = left && nums[first] == target) {
result[0] = first --;
}
// 则直接从当前位置，查找最右边的目标值
int last = mid;
while(last = right && nums[last] == target) {
result[1] = last++;
}
}
}
}
复杂度分析
时间复杂度：
O(log(n))；
空间复杂度：
O(log(n))；采用了递归
分治法（迭代）
递归版本的解法的空间复杂度为
O(log(n))，可以通过迭代将空间复杂度降到
O(1)
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] result = new int[2];
result[0] = -1;
result[1] = -1;
int left = 0;
int right = nums.length -1;
while(left = right) {
int mid = (left + right) 1;
if(nums[mid] target) {
// 右半部分继续搜索
left = mid + 1;
} else if(nums[mid] target) {
// 左半部分继续搜索
right = mid - 1;
} else {
// 左右部分均有
// 则直接从当前位置，查找最左边的目标值
int first = mid;
while(first = left && nums[first] == target) {
result[0] = first --;
}
// 则直接从当前位置，查找最右边的目标值
int last = mid;
while(last = right && nums[last] == target) {
result[1] = last++;
}
break;
}
}
return result;
}
}
复杂度分析
时间复杂度：
O(log(n))；
空间复杂度：
O(1)；
参考资料
- 在排序数组中查找元素的第一个和最后一个位置: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
原文始发于微信公众号（xiaogan的技术博客）：
