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

前往題目

想法

• 用binary search搜尋兩次
• 但我沒想到可以怎麼變化，因為一般的二元搜索沒辦法

思路

1. 兩次二元搜索，第一次找第一個，第二次找最後一個
2. 每次找到target不要急著回傳，找first就往左邊繼續找，直到l == r；找last就往右邊繼續找，一樣直到l == r

所以不會錯過第一個和最後一個

Code

網友解答

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[2];

        res[0] = findFirst(nums, target);
        res[1] = findLast(nums, target);

        return res;
    }

    private int findFirst(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int res = -1;

        while (l <= r) {
            int mid = l + (r - l) / 2;

            if (nums[mid] < target) {
                l = mid + 1;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else { // Found
                res = mid;

                // The result may not be the first occurance of the targets
                // Check thoroughly
                r = mid - 1;
            }
        }
        return res;
    }

    private int findLast(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int res = -1;

        while (l <= r) {
            int mid = l + (r - l) / 2;

            if (nums[mid] < target) {
                l = mid + 1;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else { // Found
                res = mid;

                // The result may not be the last occurance of the targets
                // Check thoroughly
                l = mid + 1;
            }
        }
        return res;
    }
}