题目描述
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
给出一个递增的int数组，找到target值的起始和结束位置。
Your algorithm's runtime complexity must be in the order of O(log n).
算法的时间复杂度要求O(log n)。
If the target is not found in the array, return [-1, -1].
如果没有找到target，返回[-1, -1]。
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
思路分析
有序数组，log n时间复杂度内找target，还是二分查找法的用法。这回数组是有重复数字的了，找范围需要找两个数，和二分查找的思路一样，分别用二分查找法找到起点和终点。以nums = [5,7,8,8,8,10], target = 8为例：
找起点时，如果nums[mid] == target，那么说明mid有可能是起点，也有可能是连续的8的中间的某一个，因此先记录mid的位置，然后再去左边查找。如果nums[mid] != target，则和普通的二分查找一样。
找终点是同理。
代码实现
public class Solution {
/**
* 88 / 88 test cases passed.
* Status: Accepted
* Runtime: 8 ms
*
* @param nums
* @param target
* @return
*/
public int[] searchRange(int[] nums, int target) {
int left = findLeft(nums, 0, nums.length - 1, target);
int right = findRight(nums, left, nums.length - 1, target);
return new int[]{left, right};
}
private int findLeft(int[] nums, int start, int end, int target) {
if (start > end) {
return -1;
}
int result;
int mid = (start + end) / 2;
if (nums[mid] == target) {
result = mid;
int res = findLeft(nums, start, mid - 1, target);
if (res != -1) {
result = res;
}
return result;
} else if (nums[mid] > target) {
return findLeft(nums, start, mid - 1, target);
} else {
return findLeft(nums, mid + 1, end, target);
}
}
private int findRight(int[] nums, int start, int end, int target) {
if (start < end) {
return -1;
}
int result;
int mid = (start + end) / 2;
if (nums[mid] == target) {
result = mid;
int res = findRight(nums, mid + 1, end, target);
if (res != -1) {
result = res;
}
return result;
} else if (nums[mid] > target) {
return findRight(nums, start, mid - 1, target);
} else {
return findRight(nums, mid + 1, end, target);
}
}
}
