[LeetCode] 34. Find First and last Position of Element in Sorted Array

前言

---

　　這題標準運用了二分搜尋法，演算法通常需要使用二分思想，即每次能夠排除一半的範圍，快速的找出陣列中所要求的元素位置，這樣時間複雜度可達 O(log n)，時間複雜度可達 O(n)，這裡有 JAVA 和 Python 的寫法。

題目

---

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.

給定一個不是降序過後的整數陣列 nums，找到目標值的開始和結束的位置。
如果在陣列裡找不到目標，回傳 [-1, -1]。
你必須寫出一個時間複雜度 O(log n) 的算法。

題目連結：https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

題目限制

---

0 <= nums.length <= 105
109 <= nums[i] <= 109
nums is a non-decreasing array.
109 <= target <= 109

範例

---

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

目標值是 8，所以在陣列裡開始和結束的位置是 3 和 4

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

Input: nums = [], target = 0
Output: [-1,-1]

思路&筆記

---

1. 設計兩個函數 findFirst 、 findLast 來取得第一個和最後一個符合 target 值的索引。
2. 兩個函數內都運用了二分搜尋法來找到正確的索引。
3. findFirst 函數：
   • 如果目標元素 target 小於等於 nums[mid]，則將 end 更新為 mid - 1。
   • 如果目標元素 target 大於 nums[mid]，則將 start 更新為 mid + 1。
   • 在找到目標元素時，將 idx 設定為 mid。
   • 確保在找到目標元素時繼續向左搜尋，以找到第一次出現的位置。
4. findLast 函數：
   • 如果目標元素 target 大於等於 nums[mid]，則將 start 更新為 mid + 1。
   • 如果目標元素 target 小於 nums[mid]，則將 end 更新為 mid - 1。
   • 在找到目標元素時，將 idx 設定為 mid。
   • 確保在找到目標元素時繼續向右搜尋，以找到最後一次出現的位置。

[注意點] 之所以要用上述中間值的寫法會比較安全，因如果 start 和 end 趨近於最大數時，兩者相加起來的合可能會造成整數溢位

JAVA 實現

---

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[2];
        result[0] = findFirst(nums, target); // target 第一次出現的位置
        result[1] = findLast(nums, target); // target 最後一次出現的位置
        return result;
    }

    public int findFirst(int[] nums, int target){
        int idx = -1; // 回傳值
        int start = 0; // 起點位置
        int end = nums.length - 1; // 終點位置
        while(start <= end){
            int mid = (start + end) / 2; // 中位數
            // 一直往陣列的左側找到底，找到第一次出現的位置
            if(target <= nums[mid]){
                end = mid - 1; // 重新定義終點，下次回圈找到新的終點停止
            }else{
                start = mid + 1; // 重新定義起點，下次回圈從新的起點開始
            }
            if (target == nums[mid]) { // 陣列裡確定有 target
                idx = mid;
            }
        }
        return idx;
    }

    public int findLast(int[] nums, int target){
        int idx = -1;
        int start = 0;
        int end = nums.length - 1;
        while (start <= end){
           int mid = (start + end) / 2;
           // 一直往陣列的右側找到底，找到最後一次出現的位置
           if(target >= nums[mid]){
               start = mid + 1;
           }else{
               end = mid - 1;
           }
           if(target == nums[mid]){
               idx = mid;
           }
        }
        return idx;
    }
}

Python 實現

---

使用了和 Java 一樣的邏輯執行，換成 Python 的寫法。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        result = [self.findFirst(nums, target), self.findLast(nums, target)]
        return result

    def findFirst(self, nums: List[int], target: int) -> int:
        idx = -1
        start, end = 0, len(nums) - 1

        while start <= end:
            mid = (start + end) // 2
            if target <= nums[mid]:
                end = mid - 1
            else:
                start = mid + 1

            if target == nums[mid]:
                idx = mid

        return idx

    def findLast(self, nums: List[int], target: int) -> int:
        idx = -1
        start, end = 0, len(nums) - 1

        while start <= end:
            mid = (start + end) // 2
            if target >= nums[mid]:
                start = mid + 1
            else:
                end = mid - 1

            if target == nums[mid]:
                idx = mid

        return idx

成績

Language	Runtime	Memory
Java	0ms	45.74MB
Python	75ms	17.81MB