題目描述
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
給出一個遞增的int數(shù)組，找到target值的起始和結(jié)束位置乏德。
Your algorithm's runtime complexity must be in the order of O(log n).
算法的時間復(fù)雜度要求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]
思路分析
有序數(shù)組，log n時間復(fù)雜度內(nèi)找target，還是二分查找法的用法。這回數(shù)組是有重復(fù)數(shù)字的了漫仆，找范圍需要找兩個數(shù)吗浩，和二分查找的思路一樣微王，分別用二分查找法找到起點和終點啊央。以nums = [5,7,8,8,8,10], target = 8為例：
找起點時乓土，如果nums[mid] == target尽棕，那么說明mid有可能是起點氧敢，也有可能是連續(xù)的8的中間的某一個唯袄，因此先記錄mid的位置，然后再去左邊查找。如果nums[mid] != target，則和普通的二分查找一樣。
找終點是同理脸爱。
代碼實現(xiàn)
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);
}
}
}
