问题描述
Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].
问题分析
在升序数组中找到target的开始下标和终止下标，没有target则返回{-1， -1}。需要时间复杂度为O(log n)，这里直接想到二分查找时间复杂度就是O(log n)，所以用两个二分查找就可以解决这个问题。
java实现
/**
* @Author: LiuYafei
* @Date: 2017/10/31
* @Time: 18:20
* @Description:
*/
public class SearchforaRange {
public static int[] searchRange(int[] nums, int target) {
if(nums == null || nums.length == 0) {
return new int[]{-1, -1};
}
if(nums.length == 1) {
if(target != nums[0]) {
return new int[]{-1,-1};
}
else
return new int[]{0,0};
}
int lo = 0;
int hi = nums.length - 1;
int[] res = new int[2];
while (lo < hi) {
int mid = (lo + hi) / 2;
if(nums[mid] < target ) {
lo = mid + 1;
}
else {
hi = mid;
}
if(hi == lo && nums[lo] != target)
return new int[]{-1, -1};
}
res[0] = lo;
lo = 0;
hi = nums.length - 1;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if(nums[mid] > target ) {
hi = mid - 1;
}
else {
lo = mid;
}
if(hi == lo && nums[lo] != target)
return new int[]{-1, -1};
}
res[1] = hi;
return res;
}
public static void main(String [] args) {
SearchforaRange.searchRange(new int[]{5,7,7,8,8,10},8 );
}
}
转载于:https://www.cnblogs.com/lyf722/p/7763198.html
相关资源：JAVA上百实例源码以及开源项目
