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]
.
A: 就是简单的二分查找,利用个数组的low,high两个index来找
--------------第二遍--------
就是对于找 findLast的时候, 对于边界问题,没考虑好 -----------回头,仔细琢磨吧
public class Solution { public int[] searchRange(int[] A, int target) { int start = findFirst(A,0,A.length -1,target); if(start <0){ int result[] = {-1,-1}; return result; } int end = findLast(A,start, A.length-1, target); int[] result = {start, end}; return result; } private int findFirst(int[] A, int begin, int end, int target){ if(begin > end) return -1; if(begin == end){ if(A[begin] == target){ return begin; }else{ return -1; } } int mid = (begin+end)/2; if(A[mid]>=target){ return findFirst(A,begin,mid,target); }else{ return findFirst(A,mid+1,end,target); } } private int findLast(int[] A, int begin, int end, int target){ if(begin > end) return -1; if(begin == end){ if(A[end] == target){ return end; }else{ return -1; } } int mid = (begin+end +1)/2; if(A[mid]<= target){ return findLast(A,mid,end,target); }else{ return findLast(A,begin,mid-1,target); } } }
----------------3rd pass-----------------------------------
public class Solution { public int[] searchRange(int[] nums, int target) { int res[] = {helper(0,nums.length-1, nums,target,true),helper(0,nums.length-1,nums,target,false)}; return res; } private int helper(int start, int end, int[] A, int target, boolean isMin){ if( start > end) return -1; int mid = (start+end)/2; if( A[mid]==target){ if(isMin){ // need check left int left = helper(start,mid-1, A, target, isMin); return left>=0?left:mid; }else{ int right = helper(mid+1, end, A, target, isMin); return right>=0?right : mid; } }else if(A[mid] < target){ return helper(mid+1,end, A,target, isMin); }else{ return helper(start,mid-1,A,target,isMin); } } }
Learned:
No comments:
Post a Comment