每天一道算法題：34. 在排序數組中查找元素的第一個和最後一個位置（Find First and Last Position of Element in Sorted Array）

1 問題

1.1 英文描述

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
           

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
           

1.2 中文描述

給定一個按照升序排列的整數數組 nums，和一個目标值 target。找出給定目标值在數組中的開始位置和結束位置。

你的算法時間複雜度必須是 O(log n) 級别。

如果數組中不存在目标值，傳回 [-1, -1]。

示例 1:

輸入: nums = [5,7,7,8,8,10], target = 8
輸出: [3,4]
           

示例 2:

輸入: nums = [5,7,7,8,8,10], target = 6
輸出: [-1,-1]
           

來源：力扣（LeetCode）

1.3 題意解析：

• 輸入為一個按照升序排列的數組，數組中可能有相同元素
• 需要在時間複雜度O(log n)的情況下，找到給定的值的第一個和最後一個索引位置
• 如果沒有找到，則傳回第一個和最後一個索引為-1

2 解答

2.1 解題思路

• 先找到target在數組中最左邊的索引
• 如果沒有找到最左邊的索引，那麼說整個數組沒有target，直接傳回[-1, -1]
• 如果找到了最左邊的索引，那麼就再去找target在數組中最右邊的索引
• 傳回找到的兩個邊界的索引位置

2.2 代碼實作：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] indexes = {-1, -1};
        int index = search(nums, target, true);
        // 如果沒找到target的最左邊索引，就直接傳回 [-1, -1]
        if (index == nums.length || nums[index] != target) {
            return indexes;
        }
        indexes[0] = index;
        // 尋找最右邊的索引，因為在尋找最右邊索引時，left = mid + 1，是以需要把加的1減去才是正确的最右邊索引
        index = search(nums, target, false) - 1;
        indexes[1] = index;
        return indexes;
    }

    /**
     * 找到target在數組中最左/右邊的索引
     *
     * @param nums   數組
     * @param target 要查找的值
     * @param flag   true表示查找最左邊，false表示查找最右邊
     * @return 找到的索引位置，沒找到傳回 -1
     */
    private int search(int[] nums, int target, boolean flag) {
        int left = 0;
        int right = nums.length;
        int mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            // 當找最左邊的索引時，隻要 target 小于等于 nums[mid] 時，就繼續找左邊（包括mid）的數組
            // 當找最右邊的索引時，隻要 target 大于等于 nums[mid] 時，就繼續找右邊的數組
            if (target < nums[mid] || (flag && target == nums[mid])) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}