在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
1
2
| 输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
|
思路: 要求O(log n)时间复杂度. 采用二分查找即可. 先通过二分查找寻找target, 如果没有找到则返回[-1, -1],否则根据找到的索引左右扩展知道不等于target为止. 返回左右拓展的最后位置即可
代码:
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
| class Solution {
public int[] searchRange(int[] nums, int target) {
int pos = midSearch(nums, target, 0, nums.length-1);
if(pos == -1) {
return new int[]{-1, -1};
}
int left = pos;
int right = pos;
boolean leftBound = false;
boolean rightBound = false;
while(!leftBound || !rightBound) {
if(left >= 0 && nums[left] == target) {
left--;
} else {
leftBound = true;
}
if(right < nums.length && nums[right] == target) {
right++;
} else {
rightBound = true;
}
}
return new int[]{left+1, right-1};
}
int midSearch(int[] nums, int target, int start, int end) {
if(start > end) {
return -1;
}
int mid = (end - start) / 2 + start;
if(nums[mid] == target) {
return mid;
} else if(nums[mid] < target) {
return midSearch(nums, target, mid+1, end);
} else{
return midSearch(nums, target, start, mid-1);
}
}
}
|