34.在排序数组中查找元素的第一个和最后一个位置
题目:给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
【34.在排序数组中查找元素的第一个和最后一个位置】分析:其实题目意思很简单，如果没有时间复杂度的限制的话，最快的方法莫过于从前往后遍历寻找第一个出现target的元素，若找到最后都没有找到目标元素则输出[-1,-1]，然后从后往前寻找第一个出现target的元素，两个元素的下标即为所求结果。
但是题目中要求时间复杂度为logn，那么我们能想到的寻找元素的方法即为二分法，但是此题二分法需要分为两部分考虑，即寻找左边的target以及右边的target。
public int[] searchRange(int[] nums, int target) {
int leftIdx = findLeftIdx(nums,target);
int rightIdx = findRightIdx(nums,target);
int[] result = {-1,-1};
if (leftIdx == nums.length || nums[leftIdx] != target) {
return result;
}
result[0] = leftIdx;
result[1] = rightIdx-1;
return result;
}
public int findLeftIdx(int[] nums,int target){
int low = 0;
int high = nums.length;
while (low < high){
int mid = (low + high)/2;
if(nums[mid] >= target){
high = mid;
}
else
low = mid + 1;
}
return low;
}
public int findRightIdx(int[] nums,int target){
int low = 0;
int high = nums.length;
while (low < high){
int mid = (low+high)/2;
if(nums[mid] > target){
high = mid;
}
else
low = mid + 1;
}
return low;
}
