Easy understanding Java solution using Binary Search.


  • 0
    Z
    public class SearchForRange {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[]{-1, -1};
        int hi = nums.length - 1;
        int lo = 0;
        while (lo <= hi) {
            int mid = (hi + lo) / 2;
            if (nums[mid] > target) {
                hi = mid - 1;
            } else if (nums[mid] < target) {
                lo = mid + 1;
            } else {
                //move forward to find the first
                int temp = mid;
    
                for (; temp >= 0 && nums[temp] == target; temp--) {
                    result[0] = temp;
                }
                //move backward to find the last
                temp = mid;
                for (; temp < nums.length && nums[temp] == target; temp++) {
                    result[1] = temp;
                }
    
                if (result[1] == -1) {
                    result[1] = result[0];
                }
                return result;
            }
        }
        return result;
    }
    
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new SearchForRange().searchRange(new int[]{5, 7, 7, 8, 8, 8, 10}, 8)));
        System.out.println(Arrays.toString(new SearchForRange().searchRange(new int[]{2, 2}, 3)));
        System.out.println(Arrays.toString(new SearchForRange().searchRange(new int[]{1}, 1)));
        System.out.println(Arrays.toString(new SearchForRange().searchRange(new int[]{1, 2}, 2)));
        System.out.println(Arrays.toString(new SearchForRange().searchRange(new int[]{3, 3}, 3)));
        System.out.println(Arrays.toString(new SearchForRange().searchRange(new int[]{1, 2, 3}, 3)));
        System.out.println(Arrays.toString(new SearchForRange().searchRange(new int[]{1, 1, 2}, 1)));
        System.out.println(Arrays.toString(new SearchForRange().searchRange(new int[]{2, 2}, 2)));
    }
    

    }


  • 0
    M

    In the worse case, this is O(n) solution. For example, the input could be [3,3,3,3,3,3] and target is 3. Actually, you could also apply binary search in your second "else" block.


Log in to reply
 

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