在排序陣列中查找元素的第一個和最后一個位置（middle）
一、題目
LeetCode 34.在排序陣列中查找元素的第一個和最后一個位置
給定一個按照升序排列的整數陣列 nums，和一個目標值 target，找出給定目標值在陣列中的開始位置和結束位置，如果陣列中不存在目標值 target，回傳 [-1, -1]，
你可以設計并實作時間復雜度為 O(log n) 的演算法解決此問題嗎？
示例 1：
輸入：nums = [5,7,7,8,8,10], target = 6
輸出：[-1,-1]
示例 2：
輸入：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]
提示：
- nums 是一個非遞減陣列
二、基礎模版 III
因為我們的判斷區間最少為2個元素，所以我們要注意回圈的執行條件
- 簡單的判斷邊界：
nums.length === 0，return -1； - 定義初始的左右邊界：
left = 0, right = nums.length - 1； - 確定執行條件：
left + 1 < right，這也意味著查找區間要存在 3 個元素； - 向左查找時：
right = mid； - 向左查找時：
left = mid； - 判斷剩下的兩個元素哪個符合目標元素，并回傳結果；
三、題解
分析模版
- 我們的目標是：尋找目標值的起始下標和終止下標，但它是可能重復的
- 針對這樣的情況，我們要將判斷拆解成查找目標首次出現的位置，和最后一次出現的位置\
- 我們講一個大問題，用拆分成2個小問題，并用二分但解決對應的問題
var searchRange = function(nums, target) {
const NO_TARGET = [-1, -1];
if (nums.length === 0) return NO_TARGET;
// 判斷首次位置
let firstPosition = findFirstPos(nums, target);
if (firstPosition < 0) return NO_TARGET;
// 獲取最終出現位置
let lastPostion = findLastPos(nums, target);
return [firstPosition, lastPostion];
};
// 首次出現目標位置，參考模板II
const findFirstPos = function(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
let mid = left + ((right - left) >> 1);
if (nums[mid] === target) {
right = mid; // 舍棄右側，留mid，不管右側是否有重復值，我們只留1個滿足條件的
} else if (nums[mid] > target) {
right = mid - 1; // 直接舍棄
} else {
left = mid + 1; // 直接舍棄
}
}
if (nums[left] === target) return left;
return -1;
}
// 首次出現目標位置，參考模板II
const findLastPos = function(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
let mid = left + ((right - left + 1) >> 1); // 注意這里 + 1是為了向上取整，因為我們要查找最后出現的元素
if (nums[mid] === target) {
left = mid; // 舍棄右側，留mid
} else if (nums[mid] > target) {
right = mid - 1; // 直接舍棄
} else {
left = mid + 1;
}
}
if (nums[left] === target) return left;
return -1;
}
四、寫在最后
本文是二分查找-模版III 的第一題，后面的幾道題的也算是本模版的微調版，加油～
如果對你有所幫助不妨給本專案的github 點個 star，這是對我最大的鼓勵
關于我
- 花名：余光
- WX：j565017805
- 沉迷 JS，水平有限，虛心學習中
其他沉淀
- JavaScript 版 LeetCode 題解
- 前端進階筆記
- CSDN
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/236610.html
標籤：其他
上一篇：?前端 html+css+js[1000個超炫酷特效] 當我學會這招,所有炫酷的特效頁面(含原始碼)都能下載下來啦!