1.自己写的方法，先用二分查找找出target对应的数组下标，然后再向前后找临界值。
时间复杂度：最好的情况下为O(logn)
最坏的情况下为O(n)
代码:
class Solution {
public int[] searchRange(int[] nums, int target) {
int mid=binarySearch(nums,target);
// System.out.println(mid);
int start=mid;
int end=mid;
if(mid==-1){
int[] result={-1,-1};
return result;
}else{
for(int i=mid;i>=0;i--){
if(i-1>=0){
if(nums[i-1]!=nums[i]){
start=i;
break;
}
}else{
start=i;
break;
}
}
if(mid-1<0){
start=mid;
}
for(int i=mid;i<nums.length;i++){
if(i+1<=nums.length-1){
if(nums[i]!=nums[i+1]){
end=i;
break;
}
}else{
end=i;
break;
}
}
if(mid+1==nums.length){
end=mid;
}
int[] result={start,end};
return result;
}
}
public static int binarySearch(int[] nums,int target){
int start=0;
int end=nums.length-1;
int mid;
while(start<=end){
mid=(start+end)/2;
if(nums[mid]==target){
return mid;
}
if(nums[mid]>target){
end=mid-1;
}else{
start=mid+1;
}
}
return -1;
}
}
2.优化版本
方法：可以直接用二分查找直接找到对应target在数组中最坐边的下标值。
然后target++；
再用二分查找找到target对应的下标值
时间复杂度：最好和最差都是O(logn)
考察点：这个题目主要是考察了对二分查找的进一步的运用
代码:
class Solution {
public int[] searchRange(int[] nums, int target) {
int mid=binarySearch(nums,target);
if(mid<0||mid>=nums.length||nums[mid]!=target){
return new int[]{-1,-1};
}
target++;
int end=binarySearch(nums,target);
if(end==nums.length-1&&nums[end]==target-1){
return new int[]{mid,end};
}else{
return new int[]{mid,end-1};
}
}
//直接用二分查找找到对应target值最左边的数组下标值
public static int binarySearch(int[] nums,int target){
int start=0;
int end=nums.length-1;
int mid;
int exit=-1;
while(start<end){
mid=(start+end)/2;
if(nums[mid]>=target){
end=mid;
}else{
start=mid+1;
}
}
return start;
}
