34. 在排序数组中查找元素的第一个和最后一个位置(两种方法记录)
法一（BP算法——使用双指针分别从前、后定位first index和last index），代码如下：
class Solution {
public int[] searchRange(int[] nums, int target) {
// the first method
int[] index = new int[]{-1,-1};
if(nums.length==0)return new int[]{-1,-1};
else{
int slow,fast;
for(slow=0;slow=slow;fast--){
if(nums[fast]==target){
index[1] = fast; // find the second index
break;
}//else if(nums[fast]<){} impossible
}
break; // important
}else if(nums[slow]>target)break;
}
}
return index;
}
}
法一由于使用遍历，可能存在遍历整个数组的可能，所以时间复杂度较高，所以有了法二，即使用二分查找来实现，代码如下：
class Solution {
public int[] searchRange(int[] nums, int target) {
// the second method
int[] index = new int[]{-1,-1};
if(nums.length==0)return new int[]{-1,-1};
else{
int slow,fast;
for(slow=0;slow=target){
if(nums[half]==target){
index[1]=half;
start = half+1;
half = (start + end)/2;
}
else{
end=half-1;
half = (start+end)/2;
}
}else{
end = half-1;
half = (start+end)/2;
}
}
if(index[0]!=-1&&index[1]==-1)index[1]=index[0];
// for(fast=nums.length-1;fast>=slow;fast--){
// if(nums[fast]==target){
// index[1] = fast; // find the second index
// break;
// }//else if(nums[fast]<){} impossible
// }
break; // important
}else if(nums[slow]>target)break;
}
}
return index;
}
}
法二写了很久，后来才发现问题——我错误地使用for循环实现二分查找，而不是使用while循环实现，另外二分查找边界也有问题，没有使用start=half+1和end=half-1而使用start=half和end=half,GG了，后来查询了复习了二分查找知识，才发现问题…
最后欢迎各位热爱做题的朋友一起讨论，
