-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSearchForARange.java
More file actions
64 lines (63 loc) · 1.88 KB
/
SearchForARange.java
File metadata and controls
64 lines (63 loc) · 1.88 KB
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package com.yangchd.leetcode.medium;
/**
* @author yangchd 2018/7/4.
*
* 34. Search for a Range
*
* 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 class SearchForARange {
class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums.length < 2) {
if (nums.length == 1 && nums[0] == target) {
return new int[]{0, 0};
} else {
return new int[]{-1, -1};
}
}
int find = -1;
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int middle = (low + high) / 2;
if (nums[middle] == target) {
find = middle;
break;
}
if (nums[middle] > target) {
high = middle - 1;
} else {
low = middle + 1;
}
}
int[] index = new int[2];
if (find != -1) {
int left = find;
int right = find;
while (left >= 0 && nums[left] == target) {
left--;
}
index[0] = left + 1;
while (right <= nums.length - 1 && nums[right] == target) {
right++;
}
index[1] = right - 1;
} else {
index = new int[]{-1, -1};
}
return index;
}
}
}