Clean and dead simple iterative solution with 2 binary searches


  • 0

    Use vanilla binary search with a slight twist; you opt for a strategy which pushes you to hunt for the target further left/right. I used an enum because it felt clean, you're welcome to use any other indicator.

        public int[] searchRange(int[] nums, int target) {
            
        	if (nums == null || nums.length == 0) return new int[]{-1, -1};
            int low = 0, high = nums.length - 1;
            int left = binarySearch(nums, low, high, target, Strategy.LEFTMOST);
            int right = binarySearch(nums, low, high, target, Strategy.RIGHTMOST);
            return new int[]{left, right};
        }
        
        private int binarySearch(int[] nums, int low, int high, int target, Strategy s) {
            int pivot = -1;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (nums[mid] == target) {
                    // you found one, there could be more though!
                    pivot = mid;
                    switch(s) {
                        case LEFTMOST: {
                            high = mid - 1;       
                            break;
                        }
                        case RIGHTMOST: {
                            low = mid + 1;
                            break;
                        }
                        default: return pivot;
                    }
                } else if (nums[mid] < target) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            return pivot;
        }
        
        static enum Strategy {
            LEFTMOST,
            RIGHTMOST;
        }
    

Log in to reply
 

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