34. Find First and Last Position of Element in Sorted Array

二刷 05/2022

Runtime: 0 ms, faster than 100.00% of Java online submissions for Find First and Last Position of Element in Sorted Array.

Memory Usage: 47.6 MB, less than 15.92% of Java online submissions for Find First and Last Position of Element in Sorted Array.

class Solution {

    public int[] searchRange(int[] nums, int target) {

        // Do binary search twice

        // 1st time find the starting position of target

        // 2nd time find the ending position of target

        int[] res = new int[]{-1, -1};

        if (nums == null || nums.length == 0) {

            return res;

        }

        res[0] = binarySearch(nums, target, true);

        if (res[0] != -1) {

            res[1] = binarySearch(nums, target, false);

        }

        return res;

    } 

    

    private int binarySearch(int[] nums, int target, boolean isFirst) {

        // Assuming is First is true

        int start = 0, end = nums.length - 1;

        while (start + 1 < end) {

            int mid = start + (end - start) / 2;

            if (nums[mid] == target) {

                if (isFirst) {

                    end = mid;

                } else {

                    start = mid;

                }

            } else if (nums[mid] < target) {

                start = mid + 1;

            } else {

                end = mid - 1;

            }

        }

        if (nums[start] != target && nums[end] != target) {

            return -1;

        }

        if (isFirst && nums[start] == target || !isFirst && nums[end] != target) {

            return start;

        } else {

            return end;

        }

    }

}

一刷

如果终止条件是 start < end 且 无法 start = mid + 1 (找最后一个符合条件的index时)， 就会infinite loop
所以这里条件必须是start + 1 < end
Stop when they are next to each other

100.00 %

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return new int[]{-1, -1};
        }
        int[] result = new int[]{-1, -1};
        // Binary Search For 2 times
        // 1-> find first occurance, 2-> find last occurance
        int left = binarySearch(nums, target, true);
        if (nums[left] == target) { // exist
            result[0] = left;
            result[1] = binarySearch(nums, target, false);
        }
        return result;
    }
   
    private int binarySearch(int[] nums, int target, boolean isStart) {
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            // 5, 7, 7, 8, 8
            int mid = start + (end - start) / 2;
            if (nums[mid] > target) {
                end = mid - 1;
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else { // nums[mid] == target
                if (isStart) {
                    end = mid;
                } else {
                    start = mid;
                }
            }
        }
        int result = start;
        if (isStart && nums[start] == target || !isStart && nums[end] != target) {
            return start;
        } else {
            return end;
        }
    }
}