首页 > 代码库 > [leetcode]Search for a Range
[leetcode]Search for a Range
Search for a Range
Given a sorted array of integers, 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].
分析：
已排序，且时间要求O(log n)，即用二分查找。二分查找上道题已经实现：[leetcode]Search Insert Position，该实现结果是，如果存在则返回其下标，如果不存在即返回其本该插入的位置下标。
这道题正统思想应该是，查找target，查到之后继续向两边查找两个边界。每个查找过程都需要用二分法。
然而本题我偷了一个懒，多开辟了O(n)的空间，完全用了[leetcode]Search Insert Position的代码
思路：
将int[]数组重新包装成double[],然后在double[]数组中查找target + 0.1和target - 0.1，这肯定是找不到的，二分法返回的都是本该插入的位置下标begin 和end，如果begin==end，则返回[-1,-1]，否则返回[begin,end - 1]。
代码如下：
1 public class Solution { 2 public int[] searchRange(int[] a, int target) { 3 if(a == null || a.length == 0) return new int[]{-1,-1}; 4 double[] aToDouble = new double[a.length]; 5 for(int i = 0; i < a.length; i++){ 6 aToDouble[i] = (double) a[i]; 7 } 8 int begin = binarySearch(aToDouble,(double)target - 0.1); 9 int end = binarySearch(aToDouble,(double)target + 0.1);10 if(begin == end){11 return new int[]{-1,-1};12 }else{13 return new int[]{begin,end - 1}; 14 }15 }16 private int binarySearch(double[] a,double target){17 int begin = 0, end = a.length - 1;18 while(begin <= end){19 int mid = (begin + end) >> 1;20 if(a[mid] > target){21 end = mid - 1;22 }else{23 begin = mid + 1;24 }25 }26 return begin;27 }28 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。