LeetCode算法第34题:在排序数组中查找元素第一个和最后一个位置

问题描述：

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8

输出: [3,4]

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6

输出: [-1,-1]

思路：

要满足算法的时间复杂度是 O(log n) 级别，还是需要使用二分法来进行查找。这道题目给出的排序数组是包含重复元素的，所以在使用二分法的过程中还需要判断中间节点的值与要查找的值相同的情况。如果是查找第一个元素，当要查找的元素的值大于等于中间节点元素值时，还需要在截取的上半部分数组中继续查找；同理，如果是查找最后一个元素，当要查找的元素值小于等于中间节点的元素的值时，也需要继续在截取的下半部分数组中继续查找。

java实现：

public int[] searchRange(int[] nums, int target) {

if(null == nums || nums.length == 0){

return new int[] {-1,-1};

}

int first = searchFirst(nums,target);

if(-1 == first){

return new int[] {-1,-1};

}

int last = searchLast(nums,target);

return new int [] {first,last};

}

private int searchFirst(int [] nums,int target){

int start = 0;

int end = nums.length - 1;

while(start + 1 < end){

int mid = (start + end) / 2;

if(nums[mid] >= target){

end = mid;

}else{

start = mid;

}

}

if(nums[start] == target) return start;

if(nums[end] == target) return end;

return -1;

}

private int searchLast(int [] nums,int target){

int start = 0;

int end = nums.length - 1;

while(start + 1 < end){

int mid = (start + end) / 2;

if(nums[mid] <= target){

start = mid;

}else{

end = mid;

}

}

if(nums[end] == target) return end;

if(nums[start] == target) return start;

return -1;

}