leetcode SearchforaRange
z
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
47
48
49
50
public class SearchforaRange {
/**
* 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:
*
* 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]
*/
public int[] searchRange(int[] nums, int target) {
int left = 0;
int right = nums.length-1;

while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] >= target) {
right = mid;
}
else {
left = mid+1;
}
}

if (right != target) return new int[]{-1, -1};

left = 0;
right = nums.length-1;
int a = right;

while (left < right) {
int mid = (left + right + 1) / 2;
if (nums[mid] <= target) {
left = mid;
}
else {
right = mid - 1;
}
}
return new int[]{};
}
}