-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathArray-34-Search for a Range
46 lines (41 loc) · 1.41 KB
/
Array-34-Search for a Range
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
Given an array of integers 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].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
=====================================================
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[]{-1, -1};
if(nums.length == 0)
return res;
int start;
int l = 0;
int r = nums.length;//二分查找插入位置, r = len;
int mid = 0;
while(l < r){
mid = l + (r - l) / 2;
if(target > nums[mid]) //二分查找第一个插入位置
l = mid + 1;
else
r = mid;
}
if(l == nums.length || nums[l] != target)
return res;
start = l;
int end;
l++; //这一趟从第一个插入位置后面开始查找, 缩小搜索范围
r = nums.length;
while(l < r){
mid = l + (r - l) / 2;
if(target < nums[mid]) //二分查找最后一个插入位置
r = mid;
else
l = mid + 1;
}
end = l - 1;
return new int[]{start, end};
}
}
//68%