2015年9月20日星期日

Leetcode 34 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: use 2 binary search. Search left and right to combine the result. Do not forget the initial judgement. if target<nums[0] or >nums[n-1] do not need search.
 public class Solution {  
   public int[] searchRange(int[] nums, int target) {  
     int lo=0, hi=nums.length-1;  
     if (target<nums[lo] || target>nums[hi]) return new int[]{-1,-1};  
     while (lo<hi) {  
       int mid=lo+(hi-lo)/2;  
       if (nums[mid]>=target) hi=mid;  
       else lo=mid+1;  
     }  
     int left=lo;  
     lo=0;  
     hi=nums.length-1;  
     while (lo<hi) {  
       int mid=hi-(hi-lo)/2;  
       if (nums[mid]<=target) lo=mid;  
       else hi=mid-1;  
     }  
     int right=lo;  
     if (left>right) return new int[]{-1,-1};  
     return new int[]{left,right};  
   }  
 }  

没有评论:

发表评论