Simple single binary search O(lgN) JAVA solution


  • 0
    S

    This solution has only one binary search, after that to find the lower and upper bounds, I simply iterated down and up from the index given.

     class Solution {
          public int[] searchRange(int[] nums, int target) {
             if (nums.length == 0) return new int[]{-1,-1};
             //binary search
             int l = 0, r = nums.length - 1;
             int index = 0;
             while (l <= r) {
                index = l + (r-l)/2;
                if (nums[index] == target) break;
                if (nums[index] < target) l = index + 1;
                 else r = index - 1;
            }
            if (index < 0 || index >= nums.length || nums[index] != target ) return new int[]{-1,-1};
            //find lower bound
            int lower_index = index;
            while(lower_index>=0 && nums[lower_index] == target){
                lower_index--;
            }
            //find upper bound
            int upper_index = index;
            while(upper_index<nums.length && nums[upper_index] == target){
                upper_index++;
            }
            return new int[]{lower_index+1,upper_index-1};
            
        }
    }
    

Log in to reply
 

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