34. Find First and Last Position of Element in Sorted Array， 这是medium题。
题目要求给出一个整数array，并且是non-decreasing order, 一个整数target，找出array中target出现的index区间。如果找不到返回【-1， -1】
这道题目比较有意思的是，它要找的是一个区间，也就是说每个值都是可以重复出现的。所以这道题其实就是两道题：找出target最早出现的地方，找出target最晚出现的地方。
通常普通的二分查找找到的就是target，是mid值，现在有重复的值的话，如果要找最早出现的，那么在找到mid后我们还要往左找，看看有没有。同理，最晚出现的，就是找到mid后，往右找，看看有没有更大的index。
solution: binary search
my solution:
class Solution {
public int[] searchRange(int[] nums, int target) {
int start = -1, end = -1;
if (nums.length == 0) {
return new int[]{start, end};
}
start = leftMostIndex(nums, target);
if(start == -1) return new int[]{-1, -1};
end = rightMostIndex(nums, target);
return new int[]{start, end};
}
private int leftMostIndex(int[] nums, int target) {
int l = 0, r = nums.length - 1, leftMost = -1;
while(l<=r) {
int mid = l + (r-l)/2;
if(target < nums[mid]) {
r = mid - 1;
} else if (target > nums[mid]) {
l = mid + 1;
} else {
leftMost = mid;
r = mid - 1;// search in the left section
}
}
return leftMost;
}
private int rightMostIndex(int[] nums, int target) {
int l = 0, r = nums.length - 1, rightMost = -1;
while(l<=r) {
int mid = l + (r-l)/2;
if(target < nums[mid]) {
r = mid - 1;
} else if (target > nums[mid]){
l = mid + 1;
} else {
rightMost = mid;
l = mid + 1;//search in the right section
}
}
return rightMost;
}
}
这边用了一个leftMost和一个rightMost来记录，因为我脑子总是转不过弯最后是取哪个数，这样子的话会容易点。
time complexity: O(logn)
space complexity: O(1)
网友评论