PattySung

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.

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]

Example 3:

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

<解題>

由於要回傳[0,1]一組陣列，使其出現target數字的起始和最後index，所以需要先建立result[0]=findStartingIndex(nums, target)和result[1]==findEndingIndex(nums, target);
兩者的方法很像過往找BTS target的題目，但不同的是，由於是要找重複的數字，所以在while(start<=end)中：

findStartingIndex，兩者數字相同時，需要再往前看一位
findEndingIndex，兩者數字相同時，需要再往後看一位

最後if(nums[mid]==target) index = mid;

<舉例說明>

假設有一個已排序的整數數組 nums 為：[1, 2, 2, 3, 4, 4, 4, 5, 6]，我們要找到目標元素 target 為 4 的起始索引和結束索引。

a.當尋找目標元素 4 的起始索引時：

start = 0, end = 8, mid = (0 + 8) / 2 = 4，nums[mid] = 4，由於目標元素為 4，將 end 更新為 mid - 1 = 3。
start = 0, end = 3, mid = (0 + 3) / 2 = 1，nums[mid] = 2，由於目標元素 4 大於 2，將 start 更新為 mid + 1 = 2。
start = 2, end = 3, mid = (2 + 3) / 2 = 2，nums[mid] = 2，由於目標元素 4 大於 2，將 start 更新為 mid + 1 = 3。
start = 3, end = 3, mid = (3 + 3) / 2 = 3，nums[mid] = 3，由於目標元素 4 大於 3，將 start 更新為 mid + 1 = 4。
start = 4, end = 3，start > end，迴圈結束，返回 index = 4。

b. 當尋找目標元素 4 的結束索引時：

start = 0, end = 8, mid = (0 + 8) / 2 = 4，nums[mid] = 4，由於目標元素為 4，將 start 更新為 mid + 1 = 5。
start = 5, end = 8, mid = (5 + 8) / 2 = 6，nums[mid] = 4，由於目標元素 4 等於 4，將 start 更新為 mid + 1 = 7。
start = 7, end = 8, mid = (7 + 8) / 2 = 7，nums[mid] = 5，由於目標元素 4 小於 5，將 end 更新為 mid - 1 = 6。
start = 7, end = 6，start > end，迴圈結束，返回 index = 6。

最終，返回結果數組 [4, 6]，表示目標元素 4 在已排序數組中的起始索引和結束索引分別為 4 和 6。

要找到陣列中，target數字的起始和終點index，


class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[2];
        result[0] = findStartingIndex(nums, target);
        result[1] = findEndingIndex(nums, target);
        return result;
    }

    public int findStartingIndex(int[] nums, int target){
        int index = -1;
        int start = 0;
        int end = nums.length-1;

        while(start<=end){
            int mid = start + (end-start)/2;
            if(nums[mid] >= target){ //對於startingIndex而言，雖然找到了element，但仍希望往左移動尋找，找到前一個target數字
                end = mid-1;
            } else{
                start = mid+1;
            }
            if(nums[mid]==target) index = mid;
        }
        return index;
    }
    public int findEndingIndex(int[] nums, int target){
        int index = -1;
    
        int start = 0;
        int end = nums.length-1;

        while(start<=end){
            int mid = start + (end-start)/2;
            if(nums[mid] <= target){ //對於endingIndex而言，雖然找到了element，但仍希望往右移動尋找，找到下一個target數字
                start = mid +1;
            } else{
                end = mid-1;
            }
            if(nums[mid]==target) index = mid;
        }

        return index;
    }
}

Time: O(log n) Space: O(1)

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

<解題>

<舉例說明>