My Java solution runs in O(logn)


  • 0
    Y
    public class Solution {
        public int[] searchRange(int[] nums, int target) {
            if(nums.length == 0) return new int[]{-1, -1};
            int start = -1, end = -1;
            int s=0, e=nums.length-1;
            while(s <= e){
            int mid = s + (e-s+1)/2;
            if(nums[mid] == target) {
                start = mid;
                end = mid;
                if(mid > 0){
                    int left = searchLeft(nums, target, 0, mid-1);
                    if(left !=-1) start = left;
                }
                if(mid < nums.length-1){
                    int right = searchRight(nums, target, mid+1, nums.length-1);
                    if(right !=-1) end = right;
                }
                break;
            }
            else if(nums[mid] > target){
                e = mid-1;
            }
            else {
                s = mid+1;
            }
            }
            return new int[]{start, end};
        }
        public int searchLeft(int[] nums, int target, int start, int end){
            if(start == end) {
                if (nums[start] == target) return start;
                else return -1;
            }
            int pos = -1;
            int mid = start + (end-start+1)/2;
            if(nums[mid] == target){
                pos = mid;
                if(mid > start){
                    int left = searchLeft(nums, target, start, mid-1);
                    if(left != -1) pos = left;
                }
            }
            else{
                if(mid < end){
                    int right = searchLeft(nums, target, mid+1, end);
                    if(right != -1) pos = right;
                }
            }
            return pos;
        }
        public int searchRight(int[] nums, int target, int start, int end){
            if(start == end) {
                if (nums[start] == target) return start;
                else return -1;
            }
            int pos = -1;
            int mid = start + (end-start+1)/2;
            if(nums[mid] == target){
                pos = mid;
                if(mid < end){
                    int right = searchRight(nums, target, mid+1, end);
                    if(right != -1) pos = right;
                }
            }
            else{
                if(mid > start){
                    int left = searchRight(nums, target, start, mid-1);
                    if(left != -1) pos = left;
                }
            }
            return pos;
            
            
        }
        
    }

Log in to reply
 

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