O(logn) solution using only one pass (recursive)


  • 0
    K
    public class Solution {
        
        public int[] search(int [] nums, int s, int e, int target) {
            int [] res = new int[] {-1, -1};
            if(s > e) return res;
            
            int mid = (s+e)/2;
            if(nums[mid] == target) {
                if(mid > 0 && nums[mid] == nums[mid-1]) {
                    int[] tmp = search(nums, s, mid-1, target); 
                    res[0] = tmp[0];
                } else {
                    res[0] = mid;
                }
                
                if(mid < e && nums[mid] == nums[mid+1]) {
                    int[] tmp = search(nums, mid+1, e, target);
                    res[1] = tmp[1];
                } else {
                    res[1] = mid;
                }
                return res;
            }
            
            if(target < nums[mid]) {
                return search(nums, s, mid-1, target);
            } else {
                return search(nums, mid+1, e, target);
            }
        }
        
        public int[] searchRange(int[] nums, int target) {
            return search(nums, 0, nums.length-1, target);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.