首页 > 代码库 > Leetcode-Search for a range
Leetcode-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].
Have you met this question in a real interview?
Analysis:
We need to do two binary search. The first finds out the left boundary and the second finds out the right boundary.
if mid==target, we then check whether mid-1==target, if yes, we then continue to search [start,mid-1] until we find the left boundary.
Solution:
1 public class Solution { 2 public int[] searchRange(int[] A, int target) { 3 int[] res = new int[]{-1,-1}; 4 if (A.length==0) return res; 5 6 int start = 0, end = A.length-1; 7 8 //Find left range. 9 10 while (start<=end){11 int mid = (start+end)/2;12 if (A[mid]==target){13 //find right range also.14 if (mid+1==A.length || A[mid+1]!=target) res[1] = mid;15 16 //Check left17 if (mid-1==-1 || A[mid-1]!=target){18 res[0]=mid;19 break;20 } else {21 end = mid-1;22 continue;23 }24 } else if (A[mid]>target) end = mid-1;25 else start = mid+1;26 }27 28 if (start>end) return res;29 if (res[0]!=-1 && res[1]!=-1) return res;30 31 //Find right32 start = 0;33 end = A.length-1;34 while (start<=end){35 int mid = (start+end)/2;36 if (A[mid]==target){37 //Check right38 if (mid+1==A.length || A[mid+1]!=target){39 res[1]=mid;40 break;41 } else {42 start = mid+1;43 continue;44 }45 } else if (A[mid]>target) end = mid-1;46 else start = mid+1;47 }48 49 return res; 50 }51 }
Leetcode-Search for a range
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。