一、題目

給你一個按照非遞減順序排列的整數(shù)數(shù)組?nums，和一個目標值?target。請你找出給定目標值在數(shù)組中的開始位置和結(jié)束位置。

如果數(shù)組中不存在目標值?target，返回?[-1, -1]。

你必須設(shè)計并實現(xiàn)時間復雜度為?O(log n)?的算法解決此問題。

示例 1：

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

示例?2：

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

示例 3：

輸入：nums = [], target = 0
輸出：[-1,-1]

二、思路解析

二分查找，它很簡單，但也很容易寫出死循環(huán)。不過，不必過多恐懼，只要多做練習，他就會是最簡單的查找算法！

我們來看這道題，主要分為 2 部分：查找區(qū)間的左端點 和 右端點。

1）查找區(qū)間左端點

左邊界劃分的兩個區(qū)間的特點：

? 左邊區(qū)間 [left, resLeft - 1] 都是?于 x 的；
? 右邊區(qū)間（包括左邊界） [resLeft, right] 都是?于等于 x 的；

因此，關(guān)于 mid 的落點，我們可以分為下?兩種情況：

? 當我們的 mid 落在 [left, resLeft - 1] 區(qū)間的時候，也就是 arr[mid] <target 。說明 [left, mid] 都是可以舍去的，此時更新 left 到 mid + 1 的位置，繼續(xù)在 [mid + 1, right] 上尋找左邊界；

? 當 mid 落在 [resLeft， right] 的區(qū)間的時候，也就是 arr[mid] >= target 。說明 [mid + 1, right] （因為 mid 可能是最終結(jié)果，不能舍去）是可以舍去的，此時更新 right 到 mid 的位置，繼續(xù)在 [left, mid] 上尋找左邊界；

注意：這?找中間元素需要向下取整，即 mid = left + ( right - left ) / 2 ，而不是?mid = left + ( right - left + 1?) / 2 。

因為后續(xù)移動左右指針的時候：
? 左指針： left = mid + 1 ，是會向后移動的，因此區(qū)間是會縮?的；
? 右指針： right = mid ，可能會原地踏步（?如：如果向上取整的話，如果剩下 1,2 兩個元
素， left == 1 ， right == 2 ， mid == 2 。更新區(qū)間之后， left，right，mid 的
值沒有改變，就會陷?死循環(huán)）。
因此?定要注意，當 right = mid 的時候，要向下取整。

2）查找區(qū)間右端點

我們先? resRight 表?右邊界；

這時可以注意到右邊界的特點：

????????? 左邊區(qū)間 （包括右邊界） [left, resRight] 都是?于等于 x 的；
????????? 右邊區(qū)間 [resRight+ 1, right] 都是?于 x 的；

因此，關(guān)于 mid 的落點，我們可以分為下?兩種情況：

? 當我們的 mid 落在 [left, resRight] 區(qū)間的時候，說明 [left, mid - 1]（ mid 不可以舍去，因為有可能是最終結(jié)果） 都是可以舍去的，此時更新 left 到 mid的位置；
? 當?mid 落在 [resRight+ 1, right] 的區(qū)間的時候，說明?[mid, right] 內(nèi)的元素是可以舍去的，此時更新?right 到?mid - 1 的位置；

? 由此，就可以通過?分，來快速尋找右邊界；
注意：這?找中間元素需要向上取整「?mid = left + ( right - left + 1?) / 2」。

因為后續(xù)移動左右指針的時候：
? 左指針： left = mid ，可能會原地踏步（比如：如果向下取整的話，如果剩下?1,2 兩個元
素， left == 1， right == 2，mid == 1 。更新區(qū)間之后， left，right，mid ?的值
沒有改變，就會陷?死循環(huán)）。
? 右指針： right = mid - 1 ，是會向前移動的，因此區(qū)間是會縮小的；
因此?定要注意，當? right = mid ?的時候，要向下取整。

三、完整代碼

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int ret[] = new int[2];
        ret[0] = ret[1] = -1;

        // 處理邊界情況
        if(nums.length == 0){
            return ret;
            }

        // 1. ?分左端點    
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid + 1; 
            }else{
                right = mid;
            }
        }

        // 判斷是否有結(jié)果
        if(nums[left] != target){
            return ret;
        }else{
            ret[0] = left;
        }

        // 2. ?分右端點
        left = 0;
        right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] <= target){
                left = mid;
            }else{
                right = mid - 1;
            }
        }
        ret[1] = right;
        return ret ;
    }
}

以上就是本篇博客的全部內(nèi)容啦，如有不足之處，還請各位指出，期待能和各位一起進步！文章來源地址http://www.zghlxwxcb.cn/news/detail-816051.html

到了這里，關(guān)于「優(yōu)選算法刷題」:在排序數(shù)組中查找元素的第一個和最后個位置的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！