@(labuladong的算法小抄)[二分]

leetcode 34. 在排序數組中查找元素的第一個和最後一個位置

題目描述

解題思路

參考：labuladong的算法小抄 P75

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) return new int[]{-1, -1};
        /* 找到目标值的起始位置 */
        int startOfTarget = findStartOfTarget(nums, target);
        /* 如果不存在target，直接傳回 */
        if (startOfTarget == -1) return new int[]{-1, -1};
        /* 找到目标值的結束位置 */
        int endOfTarget = findEndOfTarget(nums, target);

        return new int[]{startOfTarget, endOfTarget};
    }

    /* 尋找左側邊界，傳回左側邊界的起始位置 */
    private int findStartOfTarget(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        /* 搜尋區間為[left, right] */
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                /* 收縮右邊界 */
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        /* 如果找到目标值，left正好指在target處,是以要檢查left出界情況 */
        if (left >= nums.length || nums[left] != target) return -1;
       
        return left;
    }

    /* 尋找右側邊界，傳回右側邊界的結束位置 */
    private int findEndOfTarget(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        /* 搜尋區間為[left, right] */
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                /* 收縮左邊界 */
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        /* 如果找到目标值，right正好指在target處，是以要檢查right的出界情況 */
        if (right < 0 || nums[right] != target) return -1;
        
        return right;
    }
}