问题描述
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
解决思路
遇到排序数组中找元素，首推二分法。分别找首尾两个元素，获得下标后返回。
问题解惑
我当时以为findFirst和findLast两个函数一模一样，不就是if else调换了一下嘛？实则不然，关键在于if和else判断里面= 的情况不一样，导致前者可以找到第一个，后者可以找到最后一个。找个数字验证一下就明白了。
代码
class Solution {
public int[] searchRange(int[] nums, int target) {
//corner case
if(nums.length == 0 || nums == null) return new int[]{-1, -1};
int firstTarget = findFirst(nums, target);
if(firstTarget == -1) return new int[]{-1, -1};
int lastTarget = findLast(nums, target);
return new int[]{firstTarget, lastTarget};
}
public int findFirst(int[] nums, int target){
int start = 0;
int end = nums.length - 1;
while(start + 1 < end){
int mid = (end - start) / 2 + start;
if(nums[mid] < target){
start = mid;
}else{
end = mid;
}
}
if(nums[start] == target) return start;
if(nums[end] == target) return end;
return -1;
}
public int findLast(int[] nums, int target){
int start = 0;
int end = nums.length - 1;
while(start + 1 < end){
int mid = (end - start) / 2 + start;
if(nums[mid] > target){
end = mid;
}else{
start = mid;
}
}
//get the end index prioritizedly
if(nums[end] == target) return end;
if(nums[start] == target) return start;
return -1;
}
}
复杂度分析
- 时间复杂度：O(log(n))
- 空间复杂度：O(1)
