寫在前面

??最近想復習一下數據結構與算法相關的內容，找一些題來做一做。如有更好思路，歡迎指正。

---

---

一、場景描述

??給定一個按照升序排列的整數數組 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]

---

二、具體步驟

1.環境說明

名稱	說明
IntelliJ IDEA	2019.2

2.代碼

以下為Java版本實現：

public class Lc34_searchRange {public static void main() {int[] nums = new int[]{5,7,7,8,8,10};System.out.println(Arrays.toString(searchRange(nums, 8)));int[] nums1 = new int[]{5,7,7,8,8,10};System.out.println(Arrays.toString(searchRange(nums1, 6)));}/*** 思路：** 返回值值int[]** 有序數組，時間復雜度是O(log n)* 一定是借助于二分查找，找到mid* 然后從mid位置開始，lr左右指針向兩邊擴展，范圍是在在low和high之間* 返回時需要各自回退一個指針(初始化l=mid，r=mid，首次循環一定成立)** 如果找不到mid，直接返回int[]{-1, -1}*/public static int[] searchRange(int[] nums, int target) {if (target < nums[0] || target > nums[nums.length - 1]) {return new int[] {-1, -1};}int low = 0, high = nums.length - 1;while (low <= high) {// 注意移位運算符的優先級要比+-低，所以要多加一個括號int mid = low + ((high - low) >> 1);if (target == nums[mid]) {// 找到了，即target// 從mid位置開始向兩邊擴展int l = mid, r = mid;while (l >= low && nums[l] == target) {l--;}while (r <= high && nums[r] == target) {r++;}// 回退一次return new int[] {++l, --r};} else if (target < nums[mid]) {high = mid - 1;} else {low = mid + 1;}}return new int[]{-1, -1};}}

---

寫在后面

??如果本文內容對您有價值或者有啟發的話，歡迎點贊、關注、評論和轉發。您的反饋和陪伴將促進我們共同進步和成長。