LeetCode-Go 题解 34在排序数组中查找元素的第一个和最后一个位置二分查找四大变种实战【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文基于 LeetCode-Go 仓库中 leetcode/0034.Find-First-and-Last-Position-of-Element-in-Sorted-Array/README.md 的题解思路展开完整讲解 LeetCode 第 34 题「在排序数组中查找元素的第一个和最后一个位置」的 O(log n) 解法。文章不仅给出可直接运行的 Go 实现还结合仓库源码剖析二分查找的四大基础变种查找第一个等于、最后一个等于、第一个大于等于、最后一个小于等于给定值的元素并附上仓库测试用例与运行方式。读完本文你将掌握二分查找边界问题的通用套路能够举一反三解决一系列有序数组 边界定位类题目。题目与题意原题描述给定一个按照升序排列的整数数组nums和一个目标值target。找出给定目标值在数组中的开始位置和结束位置。算法的运行时复杂度必须是O(log n)级别。如果数组中不存在目标值返回[-1, -1]。示例 1Input: nums [5,7,7,8,8,10], target 8 Output: [3,4]示例 2Input: nums [5,7,7,8,8,10], target 6 Output: [-1,-1]题目大意中文要点给定升序数组nums与目标值target要求找出第一个与target相等的元素下标找出最后一个与target相等的元素下标若数组中不存在target返回[-1, -1]。由于数组有序朴素地从左到右扫描虽然能找到答案但最坏情况下需要遍历整个数组时间复杂度为 O(n)不满足题目 O(log n) 的要求。因此必须使用二分查找。解题思路二分搜索的四大基础变种这一题是经典的二分搜索变种题。二分搜索有 4 大基础变种查找第一个值等于给定值的元素查找最后一个值等于给定值的元素查找第一个大于等于给定值的元素查找最后一个小于等于给定值的元素。本题的解题思路是分别利用变种 1 和变种 2 的解法即可做出此题变种 1 负责找到target第一次出现的位置左边界变种 2 负责找到target最后一次出现的位置右边界两者拼合即为答案。题解 README 中还指出了另一种思路先用变种 1 找到第一个相等的元素然后循环往后找到最后一个与给定值相等的元素。不过后者这种方法可能会使时间复杂度下降到O(n)因为有可能数组中 n 个元素都和给定元素相同例如nums [8, 8, 8, ..., 8]且target 8的极端情况此时线性后扫会退化为全数组扫描。因此推荐直接用两次二分将两个边界都定位在 O(log n) 内。仓库源码实现剖析本仓库中该题的核心实现位于 leetcode/0034.Find-First-and-Last-Position-of-Element-in-Sorted-Array/34. Find First and Last Position of Element in Sorted Array.go包含 1 个入口函数和 4 个变种函数完整覆盖了上述四大基础变种。入口函数 searchRangefunc searchRange(nums []int, target int) []int { return []int{searchFirstEqualElement(nums, target), searchLastEqualElement(nums, target)} }searchRange直接组合两次二分searchFirstEqualElement返回左边界searchLastEqualElement返回右边界。若target不存在两个变种都会返回-1拼合结果自然就是[-1, -1]与题目要求完全一致。变种 1查找第一个值等于 target 的元素// 二分查找第一个与 target 相等的元素时间复杂度 O(logn) func searchFirstEqualElement(nums []int, target int) int { low, high : 0, len(nums)-1 for low high { mid : low ((high - low) 1) if nums[mid] target { high mid - 1 } else if nums[mid] target { low mid 1 } else { if (mid 0) || (nums[mid-1] ! target) { // 找到第一个与 target 相等的元素 return mid } high mid - 1 } } return -1 }该函数的关键在于命中nums[mid] target之后并不立即返回而是继续判断若mid 0已到数组最左端或nums[mid-1] ! target前一个元素不等于 target说明当前mid就是第一个与target相等的元素直接返回否则说明target在更靠左的位置还有出现于是收缩右边界high mid - 1继续向左搜索。从源码结构看mid : low ((high - low) 1)使用位移代替除法且先减后加可以避免low high可能造成的整数溢出同时保证mid向左取整。变种 2查找最后一个值等于 target 的元素// 二分查找最后一个与 target 相等的元素时间复杂度 O(logn) func searchLastEqualElement(nums []int, target int) int { low, high : 0, len(nums)-1 for low high { mid : low ((high - low) 1) if nums[mid] target { high mid - 1 } else if nums[mid] target { low mid 1 } else { if (mid len(nums)-1) || (nums[mid1] ! target) { // 找到最后一个与 target 相等的元素 return mid } low mid 1 } } return -1 }与变种 1 对称命中nums[mid] target后判断右邻元素若mid len(nums)-1已到数组最右端或nums[mid1] ! target后一个元素不等于 target说明当前mid就是最后一个与target相等的元素返回否则说明target在更靠右的位置还有出现收缩左边界low mid 1继续向右搜索。变种 3查找第一个大于等于 target 的元素// 二分查找第一个大于等于 target 的元素时间复杂度 O(logn) func searchFirstGreaterElement(nums []int, target int) int { low, high : 0, len(nums)-1 for low high { mid : low ((high - low) 1) if nums[mid] target { if (mid 0) || (nums[mid-1] target) { // 找到第一个大于等于 target 的元素 return mid } high mid - 1 } else { low mid 1 } } return -1 }当nums[mid] target时说明候选区间在左侧继续判断mid 0或nums[mid-1] target来确认这是第一个满足条件的下标否则收缩high。注意该函数在找不到满足条件的元素时同样返回-1。变种 4查找最后一个小于等于 target 的元素// 二分查找最后一个小于等于 target 的元素时间复杂度 O(logn) func searchLastLessElement(nums []int, target int) int { low, high : 0, len(nums)-1 for low high { mid : low ((high - low) 1) if nums[mid] target { if (mid len(nums)-1) || (nums[mid1] target) { // 找到最后一个小于等于 target 的元素 return mid } low mid 1 } else { high mid - 1 } } return -1 }与变种 3 对称用于定位最后一个满足nums[mid] target的下标。四个变种如何串联使用题解 README 明确指出4 大基础变种的实现见代码四个函数在仓库中均已实现。它们不止服务于第 34 题更是解决大量有序数组边界问题的通用零件变种 1 变种 2 组合 → 第 34 题本题变种 3 → 常用于插入位置第一个不小于某值的元素类问题如 LeetCode 35变种 4 → 常用于最后一个不大于某值的元素类问题。测试用例与验证仓库为本题提供了表格驱动风格的单元测试位于 leetcode/0034.Find-First-and-Last-Position-of-Element-in-Sorted-Array/34. Find First and Last Position of Element in Sorted Array_test.gofunc Test_Problem34(t *testing.T) { qs : []question34{ { para34{[]int{5, 7, 7, 8, 8, 10}, 8}, ans34{[]int{3, 4}}, }, { para34{[]int{5, 7, 7, 8, 8, 10}, 6}, ans34{[]int{-1, -1}}, }, { para34{[]int{8, 8, 8}, 8}, ans34{[]int{0, 2}}, }, { para34{[]int{5, 7, 7, 8, 8, 10}, 12}, ans34{[]int{-1, -1}}, }, { para34{[]int{5, 7, 7, 8, 8, 10}, 1}, ans34{[]int{-1, -1}}, }, } // ... for _, q : range qs { _, p : q.ans34, q.para34 fmt.Printf(【input】:%v 【output】:%v\n, p, searchRange(p.nums, p.target)) searchFirstGreaterElement(p.nums, p.target) searchLastLessElement(p.nums, p.target) } }测试用例覆盖了 5 种典型场景边界覆盖相当完整输入target期望输出覆盖场景[5,7,7,8,8,10]8[3,4]目标值在数组中间且出现多次[5,7,7,8,8,10]6[-1,-1]目标值不存在夹在元素之间[8,8,8]8[0,2]整个数组全是目标值左右边界都在端点[5,7,7,8,8,10]12[-1,-1]目标值大于数组中所有元素[5,7,7,8,8,10]1[-1,-1]目标值小于数组中所有元素其中第三个用例[8,8,8]正是 README 中警告的数组中 n 个元素都与 target 相同的退化场景——即使全数组相同两次二分依然保持 O(log n) 复杂度而先二分再线性后扫的方法在此场景下会退化到 O(n)这正是本实现采用两次二分的原因。如何运行测试仓库模块名为github.com/halfrost/LeetCode-Go见 go.modGo 版本要求为 1.19。进入仓库根目录后可以单题运行go test -run Test_Problem34 -v ./leetcode/0034.Find-First-and-Last-Position-of-Element-in-Sorted-Array/也可以按仓库脚本 gotest.sh 的方式对全部 leetcode 题解做覆盖测试并生成覆盖率报告go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...该脚本在注释中说明go test支持对多个包一次性-coverprofile可直接产出单个合法的覆盖率文件避免旧写法逐个包追加产生重复的mode: atomic头导致新版 Codecov 解析为 0% 覆盖率的问题。仓库根目录下的 coverage.txt 即由此生成。复杂度分析时间复杂度O(log n)。searchFirstEqualElement与searchLastEqualElement各执行一次二分查找每次迭代区间减半最坏情况下各需约 log₂n 次比较两次二分是顺序执行的常量倍关系故总复杂度仍为 O(log n)。空间复杂度O(1)。只使用了low、high、mid等常数个变量不随输入规模增长。对比一次二分找左边界 线性扫描找右边界的方案后者在最坏情况数组全部等于 target下时间复杂度退化为 O(n)不满足题目要求而两次二分方案在任何输入下都严格保持在 O(log n)。小结LeetCode 34 题是理解二分搜索边界处理的绝佳范本。通过本仓库的实现可以看到等于条件的细化命中目标后不立即返回而是通过检查相邻元素判断是否为边界这是找第一个/最后一个类变种的核心技巧四大变种互相独立、可自由组合查找第一个等于、最后一个等于、第一个大于等于、最后一个小于等于这四个函数在本仓库源码中全部实现可直接复用到其他有序数组类题目循环不变量保持一致四个变种统一采用low high的循环条件与low/high mid ± 1的收缩方式保证算法正确性与可读性。对于需要进一步巩固二分思想的读者可以参考仓库 note/grokking_algorithms.md 中的提示仅当列表是有序的时候二分查找才管用以及 note/time_complexity.md 中对二分搜索 O(log n) 复杂度的分析——它们与本题的解法原理一脉相承。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解 34：在排序数组中查找元素的第一个和最后一个位置（二分查找四大变种实战）
LeetCode-Go 题解 34在排序数组中查找元素的第一个和最后一个位置二分查找四大变种实战【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文基于 LeetCode-Go 仓库中 leetcode/0034.Find-First-and-Last-Position-of-Element-in-Sorted-Array/README.md 的题解思路展开完整讲解 LeetCode 第 34 题「在排序数组中查找元素的第一个和最后一个位置」的 O(log n) 解法。文章不仅给出可直接运行的 Go 实现还结合仓库源码剖析二分查找的四大基础变种查找第一个等于、最后一个等于、第一个大于等于、最后一个小于等于给定值的元素并附上仓库测试用例与运行方式。读完本文你将掌握二分查找边界问题的通用套路能够举一反三解决一系列有序数组 边界定位类题目。题目与题意原题描述给定一个按照升序排列的整数数组nums和一个目标值target。找出给定目标值在数组中的开始位置和结束位置。算法的运行时复杂度必须是O(log n)级别。如果数组中不存在目标值返回[-1, -1]。示例 1Input: nums [5,7,7,8,8,10], target 8 Output: [3,4]示例 2Input: nums [5,7,7,8,8,10], target 6 Output: [-1,-1]题目大意中文要点给定升序数组nums与目标值target要求找出第一个与target相等的元素下标找出最后一个与target相等的元素下标若数组中不存在target返回[-1, -1]。由于数组有序朴素地从左到右扫描虽然能找到答案但最坏情况下需要遍历整个数组时间复杂度为 O(n)不满足题目 O(log n) 的要求。因此必须使用二分查找。解题思路二分搜索的四大基础变种这一题是经典的二分搜索变种题。二分搜索有 4 大基础变种查找第一个值等于给定值的元素查找最后一个值等于给定值的元素查找第一个大于等于给定值的元素查找最后一个小于等于给定值的元素。本题的解题思路是分别利用变种 1 和变种 2 的解法即可做出此题变种 1 负责找到target第一次出现的位置左边界变种 2 负责找到target最后一次出现的位置右边界两者拼合即为答案。题解 README 中还指出了另一种思路先用变种 1 找到第一个相等的元素然后循环往后找到最后一个与给定值相等的元素。不过后者这种方法可能会使时间复杂度下降到O(n)因为有可能数组中 n 个元素都和给定元素相同例如nums [8, 8, 8, ..., 8]且target 8的极端情况此时线性后扫会退化为全数组扫描。因此推荐直接用两次二分将两个边界都定位在 O(log n) 内。仓库源码实现剖析本仓库中该题的核心实现位于 leetcode/0034.Find-First-and-Last-Position-of-Element-in-Sorted-Array/34. Find First and Last Position of Element in Sorted Array.go包含 1 个入口函数和 4 个变种函数完整覆盖了上述四大基础变种。入口函数 searchRangefunc searchRange(nums []int, target int) []int { return []int{searchFirstEqualElement(nums, target), searchLastEqualElement(nums, target)} }searchRange直接组合两次二分searchFirstEqualElement返回左边界searchLastEqualElement返回右边界。若target不存在两个变种都会返回-1拼合结果自然就是[-1, -1]与题目要求完全一致。变种 1查找第一个值等于 target 的元素// 二分查找第一个与 target 相等的元素时间复杂度 O(logn) func searchFirstEqualElement(nums []int, target int) int { low, high : 0, len(nums)-1 for low high { mid : low ((high - low) 1) if nums[mid] target { high mid - 1 } else if nums[mid] target { low mid 1 } else { if (mid 0) || (nums[mid-1] ! target) { // 找到第一个与 target 相等的元素 return mid } high mid - 1 } } return -1 }该函数的关键在于命中nums[mid] target之后并不立即返回而是继续判断若mid 0已到数组最左端或nums[mid-1] ! target前一个元素不等于 target说明当前mid就是第一个与target相等的元素直接返回否则说明target在更靠左的位置还有出现于是收缩右边界high mid - 1继续向左搜索。从源码结构看mid : low ((high - low) 1)使用位移代替除法且先减后加可以避免low high可能造成的整数溢出同时保证mid向左取整。变种 2查找最后一个值等于 target 的元素// 二分查找最后一个与 target 相等的元素时间复杂度 O(logn) func searchLastEqualElement(nums []int, target int) int { low, high : 0, len(nums)-1 for low high { mid : low ((high - low) 1) if nums[mid] target { high mid - 1 } else if nums[mid] target { low mid 1 } else { if (mid len(nums)-1) || (nums[mid1] ! target) { // 找到最后一个与 target 相等的元素 return mid } low mid 1 } } return -1 }与变种 1 对称命中nums[mid] target后判断右邻元素若mid len(nums)-1已到数组最右端或nums[mid1] ! target后一个元素不等于 target说明当前mid就是最后一个与target相等的元素返回否则说明target在更靠右的位置还有出现收缩左边界low mid 1继续向右搜索。变种 3查找第一个大于等于 target 的元素// 二分查找第一个大于等于 target 的元素时间复杂度 O(logn) func searchFirstGreaterElement(nums []int, target int) int { low, high : 0, len(nums)-1 for low high { mid : low ((high - low) 1) if nums[mid] target { if (mid 0) || (nums[mid-1] target) { // 找到第一个大于等于 target 的元素 return mid } high mid - 1 } else { low mid 1 } } return -1 }当nums[mid] target时说明候选区间在左侧继续判断mid 0或nums[mid-1] target来确认这是第一个满足条件的下标否则收缩high。注意该函数在找不到满足条件的元素时同样返回-1。变种 4查找最后一个小于等于 target 的元素// 二分查找最后一个小于等于 target 的元素时间复杂度 O(logn) func searchLastLessElement(nums []int, target int) int { low, high : 0, len(nums)-1 for low high { mid : low ((high - low) 1) if nums[mid] target { if (mid len(nums)-1) || (nums[mid1] target) { // 找到最后一个小于等于 target 的元素 return mid } low mid 1 } else { high mid - 1 } } return -1 }与变种 3 对称用于定位最后一个满足nums[mid] target的下标。四个变种如何串联使用题解 README 明确指出4 大基础变种的实现见代码四个函数在仓库中均已实现。它们不止服务于第 34 题更是解决大量有序数组边界问题的通用零件变种 1 变种 2 组合 → 第 34 题本题变种 3 → 常用于插入位置第一个不小于某值的元素类问题如 LeetCode 35变种 4 → 常用于最后一个不大于某值的元素类问题。测试用例与验证仓库为本题提供了表格驱动风格的单元测试位于 leetcode/0034.Find-First-and-Last-Position-of-Element-in-Sorted-Array/34. Find First and Last Position of Element in Sorted Array_test.gofunc Test_Problem34(t *testing.T) { qs : []question34{ { para34{[]int{5, 7, 7, 8, 8, 10}, 8}, ans34{[]int{3, 4}}, }, { para34{[]int{5, 7, 7, 8, 8, 10}, 6}, ans34{[]int{-1, -1}}, }, { para34{[]int{8, 8, 8}, 8}, ans34{[]int{0, 2}}, }, { para34{[]int{5, 7, 7, 8, 8, 10}, 12}, ans34{[]int{-1, -1}}, }, { para34{[]int{5, 7, 7, 8, 8, 10}, 1}, ans34{[]int{-1, -1}}, }, } // ... for _, q : range qs { _, p : q.ans34, q.para34 fmt.Printf(【input】:%v 【output】:%v\n, p, searchRange(p.nums, p.target)) searchFirstGreaterElement(p.nums, p.target) searchLastLessElement(p.nums, p.target) } }测试用例覆盖了 5 种典型场景边界覆盖相当完整输入target期望输出覆盖场景[5,7,7,8,8,10]8[3,4]目标值在数组中间且出现多次[5,7,7,8,8,10]6[-1,-1]目标值不存在夹在元素之间[8,8,8]8[0,2]整个数组全是目标值左右边界都在端点[5,7,7,8,8,10]12[-1,-1]目标值大于数组中所有元素[5,7,7,8,8,10]1[-1,-1]目标值小于数组中所有元素其中第三个用例[8,8,8]正是 README 中警告的数组中 n 个元素都与 target 相同的退化场景——即使全数组相同两次二分依然保持 O(log n) 复杂度而先二分再线性后扫的方法在此场景下会退化到 O(n)这正是本实现采用两次二分的原因。如何运行测试仓库模块名为github.com/halfrost/LeetCode-Go见 go.modGo 版本要求为 1.19。进入仓库根目录后可以单题运行go test -run Test_Problem34 -v ./leetcode/0034.Find-First-and-Last-Position-of-Element-in-Sorted-Array/也可以按仓库脚本 gotest.sh 的方式对全部 leetcode 题解做覆盖测试并生成覆盖率报告go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...该脚本在注释中说明go test支持对多个包一次性-coverprofile可直接产出单个合法的覆盖率文件避免旧写法逐个包追加产生重复的mode: atomic头导致新版 Codecov 解析为 0% 覆盖率的问题。仓库根目录下的 coverage.txt 即由此生成。复杂度分析时间复杂度O(log n)。searchFirstEqualElement与searchLastEqualElement各执行一次二分查找每次迭代区间减半最坏情况下各需约 log₂n 次比较两次二分是顺序执行的常量倍关系故总复杂度仍为 O(log n)。空间复杂度O(1)。只使用了low、high、mid等常数个变量不随输入规模增长。对比一次二分找左边界 线性扫描找右边界的方案后者在最坏情况数组全部等于 target下时间复杂度退化为 O(n)不满足题目要求而两次二分方案在任何输入下都严格保持在 O(log n)。小结LeetCode 34 题是理解二分搜索边界处理的绝佳范本。通过本仓库的实现可以看到等于条件的细化命中目标后不立即返回而是通过检查相邻元素判断是否为边界这是找第一个/最后一个类变种的核心技巧四大变种互相独立、可自由组合查找第一个等于、最后一个等于、第一个大于等于、最后一个小于等于这四个函数在本仓库源码中全部实现可直接复用到其他有序数组类题目循环不变量保持一致四个变种统一采用low high的循环条件与low/high mid ± 1的收缩方式保证算法正确性与可读性。对于需要进一步巩固二分思想的读者可以参考仓库 note/grokking_algorithms.md 中的提示仅当列表是有序的时候二分查找才管用以及 note/time_complexity.md 中对二分搜索 O(log n) 复杂度的分析——它们与本题的解法原理一脉相承。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考