首页 > 代码库 > 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].
SOLUTION 1:
使用改进的二分查找法。终止条件是：left < right - 1 这样结束的时候，会有2个值供我们判断。这样做的最大的好处是，不用处理各种越界问题。
感谢黄老师写出这么优秀的算法：http://answer.ninechapter.com/solutions/search-for-a-range/
请同学们一定要记住这个二分法模板，相当好用哦。
1. 先找左边界。当mid == target,将right移动到mid，继续查找左边界。
最后如果没有找到target,退出
2. 再找右边界。当mid == target,将left移动到mid，继续查找右边界。
最后如果没有找到target,退出
1 public class Solution { 2 public int[] searchRange(int[] A, int target) { 3 int[] ret = {-1, -1}; 4 5 if (A == null || A.length == 0) { 6 return ret; 7 } 8 9 int len = A.length;10 int left = 0; 11 int right = len - 1;12 13 // so when loop end, there will be 2 elements in the array.14 // search the left bound.15 while (left < right - 1) {16 int mid = left + (right - left) / 2;17 if (target == A[mid]) {18 // 如果相等，继续往左寻找边界19 right = mid;20 } else if (target > A[mid]) {21 // move right;22 left = mid;23 } else {24 right = mid;25 }26 }27 28 if (A[left] == target) {29 ret[0] = left;30 } else if (A[right] == target) {31 ret[0] = right;32 } else {33 return ret;34 }35 36 left = 0; 37 right = len - 1;38 // so when loop end, there will be 2 elements in the array.39 // search the right bound.40 while (left < right - 1) {41 int mid = left + (right - left) / 2;42 if (target == A[mid]) {43 // 如果相等，继续往右寻找右边界44 left = mid;45 } else if (target > A[mid]) {46 // move right;47 left = mid;48 } else {49 right = mid;50 }51 }52 53 if (A[right] == target) {54 ret[1] = right;55 } else if (A[left] == target) {56 ret[1] = left;57 } else {58 return ret;59 }60 61 return ret;62 }63 }
LeetCode: Search for a Range 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。