34. 在排序數組中查找元素的第一個和最后一個位置

描述

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

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

你必須設計并實現時間復雜度為 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]

提示：

• 0 <= nums.length <= 105
• -10^9 <= nums[i] <= 10^9
• nums 是一個非遞減數組
• -10^9 <= target <= 10^9

解題思路

算法分析

這道題是二分查找和邊界查找的經典應用。主要解法包括：

1. 雙重二分查找法：分別查找左邊界和右邊界
2. 單次二分查找法：一次查找確定范圍
3. 線性查找法：暴力遍歷（不滿足時間復雜度要求）
4. 庫函數法：使用內置的查找函數

問題本質分析

雙重二分查找詳解

flowchart TDA[輸入nums和target] --> B[查找左邊界]B --> C[left_bound = findLeft]C --> D{左邊界是否存在}D -->|不存在| E[返回[-1,-1]]D -->|存在| F[查找右邊界]F --> G[right_bound = findRight]G --> H[返回[left_bound, right_bound]]B --> I[左邊界二分查找]I --> J[尋找第一個>=target的位置]F --> K[右邊界二分查找]K --> L[尋找最后一個<=target的位置]

左邊界查找過程

flowchart TDA[左邊界查找] --> B[初始化left=0, right=len]B --> C{left < right}C -->|否| D[返回left]C -->|是| E[計算mid = left + (right-left)/2]E --> F{nums[mid] < target}F -->|是| G[left = mid + 1]F -->|否| H[right = mid]G --> CH --> CD --> I[檢查邊界有效性]

右邊界查找過程

flowchart TDA[右邊界查找] --> B[初始化left=0, right=len]B --> C{left < right}C -->|否| D[返回left-1]C -->|是| E[計算mid = left + (right-left)/2]E --> F{nums[mid] <= target}F -->|是| G[left = mid + 1]F -->|否| H[right = mid]G --> CH --> CD --> I[檢查邊界有效性]

算法流程圖

flowchart TDA[開始] --> B[輸入驗證]B --> C{數組為空}C -->|是| D[返回[-1,-1]]C -->|否| E[查找左邊界]E --> F[二分查找第一個>=target]F --> G{找到有效位置}G -->|否| DG -->|是| H{nums[left]==target}H -->|否| DH -->|是| I[查找右邊界]I --> J[二分查找最后一個<=target]J --> K[返回[left, right]]

邊界情況分析

graph TDA[邊界情況] --> B[空數組]A --> C[單元素數組]A --> D[目標不存在]A --> E[全部相同元素]A --> F[目標在首尾]B --> G[直接返回[-1,-1]]C --> H[判斷唯一元素是否匹配]D --> I[兩次二分都找不到]E --> J[返回[0, n-1]]F --> K[邊界處理要準確]

各種解法對比

二分查找變種詳解

graph TDA[二分查找變種] --> B[查找確切值]A --> C[查找左邊界]A --> D[查找右邊界]A --> E[查找插入位置]B --> F[nums[mid] == target時直接返回]C --> G[nums[mid] >= target時收縮右邊界]D --> H[nums[mid] <= target時收縮左邊界]E --> I[找到第一個>target的位置]F --> J[經典二分查找]G --> K[左邊界二分]H --> L[右邊界二分]I --> M[插入位置二分]

時間復雜度分析

• 雙重二分查找：O(log n)，執行兩次獨立的二分查找
• 單次二分查找：O(log n)，一次遍歷確定范圍
• 線性查找：O(n)，不滿足題目要求
• 庫函數查找：O(log n)，依賴具體實現

空間復雜度分析

• 雙重二分查找：O(1)，只使用常數額外空間
• 單次二分查找：O(1)，只使用常數額外空間
• 線性查找：O(1)，只使用常數額外空間
• 庫函數查找：O(1)，通常只使用常數空間

關鍵優化點

實際應用場景

二分查找模板

flowchart TDA[二分查找模板選擇] --> B[左閉右閉 [left, right]]A --> C[左閉右開 [left, right)]A --> D[左開右開 (left, right)]B --> E[right = len - 1]C --> F[right = len]D --> G[left = -1, right = len]E --> H[while left <= right]F --> I[while left < right]G --> IH --> J[經典二分模板]I --> K[邊界查找模板]

算法擴展

測試用例設計

常見錯誤避免

代碼實現要點

1. 二分查找模板：

   • 使用左閉右開區間避免邊界錯誤
   • mid計算使用left + (right-left)/2防溢出
   • 明確left和right的更新規則

2. 邊界查找邏輯：

   • 左邊界：找第一個大于等于target的位置
   • 右邊界：找最后一個小于等于target的位置
   • 驗證找到的位置是否有效

3. 特殊情況處理：

   • 空數組直接返回[-1,-1]
   • 目標值不存在返回[-1,-1]
   • 單元素數組的邊界情況

4. 性能優化技巧：

   • 提前判斷邊界情況
   • 使用位運算優化除法
   • 減少重復的邊界檢查

手工驗證示例

這個問題的關鍵在于理解二分查找的邊界處理和掌握左右邊界的查找技巧，通過兩次二分查找分別確定目標值的起始和結束位置。

完整題解代碼

package mainimport ("fmt""sort""strings""time"
)// 解法一：雙重二分查找法（推薦解法）
// 時間復雜度：O(log n)，空間復雜度：O(1)
func searchRange(nums []int, target int) []int {if len(nums) == 0 {return []int{-1, -1}}// 查找左邊界leftBound := findLeftBound(nums, target)if leftBound == -1 {return []int{-1, -1}}// 查找右邊界rightBound := findRightBound(nums, target)return []int{leftBound, rightBound}
}// 查找左邊界：第一個大于等于target的位置
func findLeftBound(nums []int, target int) int {left, right := 0, len(nums)for left < right {mid := left + (right-left)/2if nums[mid] < target {left = mid + 1} else {right = mid}}// 檢查找到的位置是否有效if left < len(nums) && nums[left] == target {return left}return -1
}// 查找右邊界：最后一個小于等于target的位置
func findRightBound(nums []int, target int) int {left, right := 0, len(nums)for left < right {mid := left + (right-left)/2if nums[mid] <= target {left = mid + 1} else {right = mid}}// left-1是最后一個小于等于target的位置return left - 1
}// 解法二：優化的雙重二分查找（更清晰的邊界處理）
// 時間復雜度：O(log n)，空間復雜度：O(1)
func searchRangeOptimized(nums []int, target int) []int {if len(nums) == 0 {return []int{-1, -1}}// 使用統一的二分查找模板leftBound := binarySearchLeft(nums, target)rightBound := binarySearchRight(nums, target)if leftBound <= rightBound {return []int{leftBound, rightBound}}return []int{-1, -1}
}// 二分查找左邊界（左閉右閉區間）
func binarySearchLeft(nums []int, target int) int {left, right := 0, len(nums)-1for left <= right {mid := left + (right-left)/2if nums[mid] >= target {right = mid - 1} else {left = mid + 1}}// 檢查邊界和目標值if left < len(nums) && nums[left] == target {return left}return len(nums) // 表示未找到
}// 二分查找右邊界（左閉右閉區間）
func binarySearchRight(nums []int, target int) int {left, right := 0, len(nums)-1for left <= right {mid := left + (right-left)/2if nums[mid] <= target {left = mid + 1} else {right = mid - 1}}// 檢查邊界和目標值if right >= 0 && nums[right] == target {return right}return -1 // 表示未找到
}// 解法三：單次二分查找法
// 時間復雜度：O(log n)，空間復雜度：O(1)
func searchRangeSingle(nums []int, target int) []int {if len(nums) == 0 {return []int{-1, -1}}// 先用標準二分查找找到任意一個target位置pos := binarySearch(nums, target)if pos == -1 {return []int{-1, -1}}// 從找到的位置向兩邊擴展left, right := pos, pos// 向左擴展找到左邊界for left > 0 && nums[left-1] == target {left--}// 向右擴展找到右邊界for right < len(nums)-1 && nums[right+1] == target {right++}return []int{left, right}
}// 標準二分查找
func binarySearch(nums []int, target int) int {left, right := 0, len(nums)-1for left <= right {mid := left + (right-left)/2if nums[mid] == target {return mid} else if nums[mid] < target {left = mid + 1} else {right = mid - 1}}return -1
}// 解法四：使用Go標準庫
// 時間復雜度：O(log n)，空間復雜度：O(1)
func searchRangeStdLib(nums []int, target int) []int {if len(nums) == 0 {return []int{-1, -1}}// 使用sort.SearchInts查找左邊界leftBound := sort.SearchInts(nums, target)// 檢查是否找到目標值if leftBound >= len(nums) || nums[leftBound] != target {return []int{-1, -1}}// 查找右邊界：第一個大于target的位置減1rightBound := sort.SearchInts(nums, target+1) - 1return []int{leftBound, rightBound}
}// 解法五：線性查找法（不滿足時間復雜度要求，僅用于對比）
// 時間復雜度：O(n)，空間復雜度：O(1)
func searchRangeLinear(nums []int, target int) []int {left, right := -1, -1// 從左到右找第一個目標值for i := 0; i < len(nums); i++ {if nums[i] == target {left = ibreak}}if left == -1 {return []int{-1, -1}}// 從右到左找最后一個目標值for i := len(nums) - 1; i >= 0; i-- {if nums[i] == target {right = ibreak}}return []int{left, right}
}// 解法六：遞歸二分查找
// 時間復雜度：O(log n)，空間復雜度：O(log n)
func searchRangeRecursive(nums []int, target int) []int {if len(nums) == 0 {return []int{-1, -1}}left := findLeftBoundRecursive(nums, target, 0, len(nums)-1)if left == -1 {return []int{-1, -1}}right := findRightBoundRecursive(nums, target, 0, len(nums)-1)return []int{left, right}
}// 遞歸查找左邊界
func findLeftBoundRecursive(nums []int, target, left, right int) int {if left > right {return -1}mid := left + (right-left)/2if nums[mid] == target {// 檢查是否是最左邊的if mid == 0 || nums[mid-1] != target {return mid}return findLeftBoundRecursive(nums, target, left, mid-1)} else if nums[mid] < target {return findLeftBoundRecursive(nums, target, mid+1, right)} else {return findLeftBoundRecursive(nums, target, left, mid-1)}
}// 遞歸查找右邊界
func findRightBoundRecursive(nums []int, target, left, right int) int {if left > right {return -1}mid := left + (right-left)/2if nums[mid] == target {// 檢查是否是最右邊的if mid == len(nums)-1 || nums[mid+1] != target {return mid}return findRightBoundRecursive(nums, target, mid+1, right)} else if nums[mid] < target {return findRightBoundRecursive(nums, target, mid+1, right)} else {return findRightBoundRecursive(nums, target, left, mid-1)}
}// 測試函數
func testSearchRange() {testCases := []struct {nums     []inttarget   intexpected []intdesc     string}{{[]int{5, 7, 7, 8, 8, 10}, 8, []int{3, 4}, "示例1：目標存在多個"},{[]int{5, 7, 7, 8, 8, 10}, 6, []int{-1, -1}, "示例2：目標不存在"},{[]int{}, 0, []int{-1, -1}, "示例3：空數組"},{[]int{1}, 1, []int{0, 0}, "單元素匹配"},{[]int{1}, 2, []int{-1, -1}, "單元素不匹配"},{[]int{1, 1, 1, 1, 1}, 1, []int{0, 4}, "全部相同元素"},{[]int{1, 2, 3, 4, 5}, 1, []int{0, 0}, "目標在首位"},{[]int{1, 2, 3, 4, 5}, 5, []int{4, 4}, "目標在末位"},{[]int{1, 2, 3, 4, 5}, 3, []int{2, 2}, "目標在中間單個"},{[]int{1, 2, 2, 2, 3}, 2, []int{1, 3}, "目標在中間多個"},{[]int{1, 3, 5, 7, 9}, 4, []int{-1, -1}, "目標在間隙"},{[]int{1, 1, 2, 2, 3, 3}, 2, []int{2, 3}, "連續重復"},{[]int{-1, 0, 3, 5, 9, 12}, 9, []int{4, 4}, "包含負數"},{[]int{-3, -1, 0, 3, 5}, -1, []int{1, 1}, "負數目標"},{[]int{0, 0, 0, 1, 1, 1}, 0, []int{0, 2}, "零值連續"},}fmt.Println("=== 查找元素范圍測試 ===\n")for i, tc := range testCases {// 測試主要解法result1 := searchRange(tc.nums, tc.target)result2 := searchRangeOptimized(tc.nums, tc.target)result3 := searchRangeStdLib(tc.nums, tc.target)status := "?"if !equalSlices(result1, tc.expected) {status = "?"}fmt.Printf("測試 %d: %s\n", i+1, tc.desc)fmt.Printf("輸入: nums=%v, target=%d\n", tc.nums, tc.target)fmt.Printf("期望: %v\n", tc.expected)fmt.Printf("雙重二分: %v\n", result1)fmt.Printf("優化二分: %v\n", result2)fmt.Printf("標準庫法: %v\n", result3)fmt.Printf("結果: %s\n", status)fmt.Println(strings.Repeat("-", 40))}
}// 輔助函數：比較兩個切片是否相等
func equalSlices(a, b []int) bool {if len(a) != len(b) {return false}for i := range a {if a[i] != b[i] {return false}}return true
}// 性能測試
func benchmarkSearchRange() {fmt.Println("\n=== 性能測試 ===\n")// 構造測試數據testData := []struct {nums   []inttarget intdesc   string}{{generateSortedArray(1000, 5), 5, "1000元素數組"},{generateSortedArray(10000, 50), 50, "10000元素數組"},{generateSortedArray(100000, 500), 500, "100000元素數組"},{generateRepeatedArray(50000, 42), 42, "50000重復元素"},}algorithms := []struct {name stringfn   func([]int, int) []int}{{"雙重二分", searchRange},{"優化二分", searchRangeOptimized},{"標準庫法", searchRangeStdLib},{"遞歸二分", searchRangeRecursive},{"線性查找", searchRangeLinear},}for _, data := range testData {fmt.Printf("%s:\n", data.desc)for _, algo := range algorithms {start := time.Now()result := algo.fn(data.nums, data.target)duration := time.Since(start)fmt.Printf("  %s: %v, 耗時: %v\n", algo.name, result, duration)}fmt.Println()}
}// 生成有序數組（包含重復元素）
func generateSortedArray(size, targetCount int) []int {nums := make([]int, size)target := size / 2for i := 0; i < size; i++ {if i >= target && i < target+targetCount {nums[i] = target} else if i < target {nums[i] = i} else {nums[i] = i - targetCount + 1}}return nums
}// 生成重復元素數組
func generateRepeatedArray(size, value int) []int {nums := make([]int, size)for i := range nums {if i < size/3 {nums[i] = value - 1} else if i < 2*size/3 {nums[i] = value} else {nums[i] = value + 1}}return nums
}// 演示二分查找過程
func demonstrateBinarySearch() {fmt.Println("\n=== 二分查找過程演示 ===")nums := []int{5, 7, 7, 8, 8, 10}target := 8fmt.Printf("數組: %v, 目標: %d\n", nums, target)fmt.Println("\n查找左邊界過程:")demonstrateLeftBound(nums, target)fmt.Println("\n查找右邊界過程:")demonstrateRightBound(nums, target)result := searchRange(nums, target)fmt.Printf("\n最終結果: %v\n", result)
}func demonstrateLeftBound(nums []int, target int) {left, right := 0, len(nums)step := 1fmt.Printf("初始: left=%d, right=%d\n", left, right)for left < right {mid := left + (right-left)/2fmt.Printf("步驟%d: left=%d, right=%d, mid=%d, nums[%d]=%d\n",step, left, right, mid, mid, nums[mid])if nums[mid] < target {left = mid + 1fmt.Printf("       nums[%d]=%d < %d, left=%d\n", mid, nums[mid], target, left)} else {right = midfmt.Printf("       nums[%d]=%d >= %d, right=%d\n", mid, nums[mid], target, right)}step++}if left < len(nums) && nums[left] == target {fmt.Printf("找到左邊界: %d\n", left)} else {fmt.Println("未找到目標值")}
}func demonstrateRightBound(nums []int, target int) {left, right := 0, len(nums)step := 1fmt.Printf("初始: left=%d, right=%d\n", left, right)for left < right {mid := left + (right-left)/2fmt.Printf("步驟%d: left=%d, right=%d, mid=%d, nums[%d]=%d\n",step, left, right, mid, mid, nums[mid])if nums[mid] <= target {left = mid + 1fmt.Printf("       nums[%d]=%d <= %d, left=%d\n", mid, nums[mid], target, left)} else {right = midfmt.Printf("       nums[%d]=%d > %d, right=%d\n", mid, nums[mid], target, right)}step++}rightBound := left - 1fmt.Printf("找到右邊界: %d\n", rightBound)
}func main() {fmt.Println("34. 在排序數組中查找元素的第一個和最后一個位置")fmt.Println("================================================")// 基礎功能測試testSearchRange()// 性能對比測試benchmarkSearchRange()// 二分查找過程演示demonstrateBinarySearch()// 展示算法特點fmt.Println("\n=== 算法特點分析 ===")fmt.Println("1. 雙重二分：經典解法，兩次獨立二分查找，清晰易懂")fmt.Println("2. 優化二分：統一模板，邊界處理更加清晰")fmt.Println("3. 標準庫法：利用內置函數，代碼簡潔")fmt.Println("4. 遞歸二分：遞歸實現，代碼簡潔但有棧溢出風險")fmt.Println("5. 線性查找：時間復雜度O(n)，不滿足題目要求")fmt.Println("\n=== 關鍵技巧總結 ===")fmt.Println("? 左邊界查找：找第一個>=target的位置")fmt.Println("? 右邊界查找：找最后一個<=target的位置")fmt.Println("? 邊界檢查：確保找到的位置值等于target")fmt.Println("? 溢出防護：mid計算使用left+(right-left)/2")fmt.Println("? 模板統一：使用一致的二分查找邊界處理")
}