05 August 2008
Given an array of integers ‘nums’ sorted in ascending order, find the starting and ending position of a given ‘target’ value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
1
2
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
1
2
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
已经升序排好的数组里面可能有重复的数字，找到给定的target值的起始下标和结束下标。没有就返回[-1， -1]，如果只有一个则返回两个同样的下标。要求复杂度为O(logn)。
1）暴力法直接遍历：直接用for循环从左到右遍历，时间复杂度为O(n)，所以会超时。先找记录第一次nums[i] = target，result[0] = i，之后继续遍历，直至nums[i] != target，result[1] = i。
2）二分查找法：做两次二分查找分别找左边界和右边界，分别特殊处理当nums[mid] == target的情况；对于查找左边界的二分查找，当nums[mid]== target的时候，移动右下标right为mid - 1；对于查找右边界的二分查找，当nums[mid] == target的时候，移动做下标left为mid + 1；注意在两个二分查找过程中，每次nums[mid] == target时都需要更新result，
两个二分查找，Time：2 × O(logn) = O(logn)，Space：O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public int[] searchRange(int[] nums, int target) {
int[] result = {-1, -1};
if (nums == null || nums.length == 0) {
return result;
}
int left = 0;
int right = nums.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) { // 找左边界，找到了一个target，还需要继续往左边找
right = mid;
} else {
left = mid;
}
}
// 这个模板left和right都可能是target，先判断右边界再判断左边界，以免可能正确的更左的左边界left被覆盖
if (nums[right] == target) {
result[0] = right;
}
if (nums[left] == target) {
result[0] = left;
}
left = 0;
right = nums.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) { // 找右边界，找到了一个target，还需要继续往右边找
left = mid;
} else {
right = mid;
}
}
// 这个模板left和right都可能是target，先判断左边界再判断右边界，以免更右的右边界right被覆盖
if (nums[left] == target) {
result[1] = left;
}
if (nums[right] == target) {
result[1] = right;
}
return result;
}