LeetCode - Find First and Last Position of Element in Sorted Array
Problem description
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]
Analysis
Basic idea is to use a floor and ceiling binary search to find the first target and the last target.
Here’s the code:
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
public class FindFirstandLastPositionofElementinSortedArray {
public int[] searchRange(int[] nums, int target) {
int left = 0, right = nums.length - 1;
int[] res = new int[2];
Arrays.fill(res, -1);
res[0] = findLeft(nums, target);
res[1] = findRight(nums, target);
return res;
}
int findLeft(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
if (mid == 0 || nums[mid - 1] < target) {
return nums[mid] == target ? mid : -1;
}
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
int findRight(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
if (mid == nums.length - 1 || nums[mid + 1] > target) {
return nums[mid] == target ? mid : -1;
}
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
Another solution from LeetCode is to use one function but a flag to find left and right, here’s the code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[]{-1, -1};
int left = insertIndex(nums, target, true);
if (left == nums.length || nums[left] != target) return res;
res[0] = left;
res[1] = insertIndex(nums, target, false) - 1;
return res;
}
private int insertIndex(int[] nums, int target, boolean left) {
int lo = 0, hi = nums.length;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (nums[mid] > target || (left && nums[mid] == target)) hi = mid;
else lo = mid + 1;
}
return lo;
}
}
Basically, it uses a boolean to decide the next branch is left or right.
What to improve
- binary search ceiling and floor, another post about this will be available soon.