首页 > 代码库 > 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].
Analysis: 这道题是二分查找Search Insert Position的变体，思路并不复杂，就是先用二分查找找到其中一个target，然后再往左右找到target的边缘。找边缘的方法跟二分查找仍然是一样的，只是相等的情况依然要往左找（找左边缘）或往右找（找右边缘）。这样下来总共进行了三次二分查找，所以算法的时间复杂度仍是O(logn)，空间复杂度是O(1)。
Notice: 对停止的边界条件极不熟悉，需要总结，参见Binary Search的Summary
1 public class Solution { 2 public int[] searchRange(int[] A, int target) { 3 int start = 0, end = A.length - 1; 4 int[] result = new int[2]; 5 result[0] = -1; 6 result[1] = -1; 7 if(A==null || A.length==0) 8 { 9 return result;10 }11 int middle = search(A, start, end, target, result);12 if (middle == -1) return result;13 result[0] = searchleft(A, 0, middle, target);14 result[1] = searchright(A, middle, A.length-1, target);15 return result;16 }17 18 public int search(int[] A, int start, int end, int target, int[] result) {19 int mid = -1;20 if (start <= end) {21 mid = (start + end) / 2;22 if (A[mid] == target) {23 result[0] = mid;24 result[1] = mid;25 return mid;26 }27 else if (A[mid] < target) {28 start = mid + 1;29 return search(A, start, end, target, result);30 }31 else {32 end = mid - 1;33 return search(A, start, end, target, result);34 }35 }36 else {37 result[0] = -1;38 result[1] = -1;39 return mid;40 }41 42 }43 44 public int searchleft(int[] A, int start, int end, int target) {45 if (start > end) return start;46 int mid = (start + end) / 2;47 if (A[mid] < target) {48 start = mid + 1;49 return searchleft(A, start, end, target);50 }51 else {52 end = mid - 1;53 return searchleft(A, start, end, target);54 }55 }56 57 public int searchright(int[] A, int start, int end, int target) {58 if (start > end) return end;59 int mid = (start + end) / 2;60 if (A[mid] <= target) {61 start = mid + 1;62 return searchright(A, start, end, target);63 }64 else {65 end = mid - 1;66 return searchright(A, start, end, target);67 }68 }69 }
如果找到target元素之后寻找边界，搜索范围过大，可以把搜索范围缩小到找到target之前最近一次(start, end)区间内，如下：
1 public class Solution { 2 public int[] searchRange(int[] A, int target) { 3 int start = 0, end = A.length - 1; 4 int[] result = new int[2]; 5 result[0] = -1; 6 result[1] = -1; 7 if(A==null || A.length==0) 8 { 9 return result;10 }11 int[] range = new int[2];12 int middle = search(A, start, end, target, range);13 if (middle == -1) return result;14 result[0] = searchleft(A, range[0], middle, target);15 result[1] = searchright(A, middle, range[1], target);16 return result;17 }18 19 public int search(int[] A, int start, int end, int target, int[] range) {20 range[0] = start;21 range[1] = end;22 int mid = -1;23 if (start <= end) {24 mid = (start + end) / 2;25 if (A[mid] == target) {26 return mid;27 }28 else if (A[mid] < target) {29 start = mid + 1;30 return search(A, start, end, target, range);31 }32 else {33 end = mid - 1;34 return search(A, start, end, target, range);35 }36 }37 else {38 return mid;39 }40 41 }42 43 public int searchleft(int[] A, int start, int end, int target) {44 if (start > end) return start;45 int mid = (start + end) / 2;46 if (A[mid] < target) {47 start = mid + 1;48 return searchleft(A, start, end, target);49 }50 else {51 end = mid - 1;52 return searchleft(A, start, end, target);53 }54 }55 56 public int searchright(int[] A, int start, int end, int target) {57 if (start > end) return end;58 int mid = (start + end) / 2;59 if (A[mid] <= target) {60 start = mid + 1;61 return searchright(A, start, end, target);62 }63 else {64 end = mid - 1;65 return searchright(A, start, end, target);66 }67 }68 }
如果想用iterative的方法来写：
1 public class Solution { 2 public int[] searchRange(int[] A, int target) { 3 int[] res = new int[2]; 4 res[0] = -1; 5 res[1] = -1; 6 if(A==null || A.length==0) 7 { 8 return res; 9 }10 int l=0;11 int r=A.length-1;12 int m=(l+r)/2;13 while(l<=r)14 {15 m=(l+r)/2;16 if(A[m]==target)17 {18 res[0]=m;19 res[1]=m;20 break;21 }22 else if(A[m]>target)23 {24 r = m-1;25 }26 else27 {28 l = m+1;29 }30 }31 if(A[m]!=target)32 return res;33 int newL = m;34 int newR = A.length-1;35 while(newL<=newR)36 {37 int newM=(newL+newR)/2;38 if(A[newM]==target)39 {40 newL = newM+1;41 }42 else43 {44 newR = newM-1;45 } 46 }47 res[1]=newR;48 newL = 0;49 newR = m;50 while(newL<=newR)51 {52 int newM=(newL+newR)/2;53 if(A[newM]==target)54 {55 newR = newM-1;56 }57 else58 {59 newL = newM+1;60 } 61 }62 res[0]=newL; 63 64 return res;65 66 }67 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。