Simple solution with one binary search O(log n) (Java)


  • 0

    Simple solution using binary search. Searching for the range in single pass.

    class Solution {
        public int[] searchRange(int[] nums, int target) {
            int[] range = {-1, -1};
    
            if (nums.length < 1) {
                return range;
            }
    
            return findRange(nums, target, 0, nums.length, range);
        }
        
        private static int[] findRange(int[] array, int target, int startFrom, int endTo, int[] range) {
            int half = (startFrom + endTo) / 2;
    
            if (array[half] == target) {
                if (range[0] == -1 && range[1] == -1) {
                    // initialize range with first found index
                    range[0] = half;
                    range[1] = half;
                }
    
                // the left border of the range can only be extended to the left
                range[0] = range[0] > half ? half : range[0];
                // the right border of the range can only be extended to the right
                range[1] = range[1] > half ? range[1] : half;
    
                if (endTo - startFrom < 2) return range;
    
                // search target left
                range = findRange(array, target, half, endTo, range);
    
                // search target right
                range = findRange(array, target, startFrom, half, range);
    
            }
            else if (array[half] < target && endTo - startFrom > 1) {
                
                return findRange(array, target, half, endTo, range);
                
            }
            else if (array[half] > target && endTo - startFrom > 1) {
                
                return findRange(array, target, startFrom, half, range);
                
            }
            return range;
        }
    }
    

Log in to reply
 

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