JAVA BINARY SEARCH SOLUTION


  • 0
    S
    public class Solution {
        public int[] searchRange(int[] nums, int target) {
            int[] res = {-1,-1}; 
            if(nums.length == 0)
                return res;
            int position = dichotomy(nums,target,0,nums.length-1);
            if(position == -1)
                return res;
            
            int start = position,end = position;
            while(start != 0 && nums[start-1]==target)
                start--;
            while(end != nums.length-1 && nums[end+1] == target)
                end++;
            res[0] = start;
            res[1] = end;
            return res;
        }
        
        private int dichotomy(int[] nums, int target, int start, int end){
            if(start == end && nums[start] != target)
                return -1;
            int parti =  (end+start)/2;
            if(nums[parti] < target)
                return dichotomy(nums,target,parti+1,end);
            else if(nums[parti] > target)
                return dichotomy(nums,target,start,parti);
            else 
                return parti;
        } 
    }

  • 0
    W

    This is not O(logn) solution though you are using binary search to check if the target exists.

    Searching the target would take logn time for sure.
    The second part depends on how many such targets exist in the array. If all the numbers are same, the second part would do n work, making it O(n) overall.


Log in to reply
 

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