浙江省网站备案流程,wordpress focus主题,龙华建设局网站,西安中风险地区有哪些文章目录704.二分查找题目#xff1a;思路#xff1a;代码实现#xff08;Go#xff09;#xff1a;34.在排序数组中查找元素的第一个和最后一个位置题目#xff1a;思路#xff1a;代码实现#xff08;Go#xff09;#xff1a;704.二分查找 题目#xff1a; 给定…文章目录704.二分查找题目思路代码实现Go34.在排序数组中查找元素的第一个和最后一个位置题目思路代码实现Go704.二分查找题目给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果 target 存在返回下标否则返回 -1。你必须编写一个具有 O(log n) 时间复杂度的算法。示例 1:输入: nums [-1,0,3,5,9,12], target 9输出: 4解释: 9 出现在 nums 中并且下标为 4示例 2:输入: nums [-1,0,3,5,9,12], target 2输出: -1解释: 2 不存在 nums 中因此返回 -1提示你可以假设 nums 中的所有元素是不重复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。思路二分查找的前提是数组有序且无重复题目已满足核心是「每次把搜索范围缩小一半」时间复杂度O(log n)。用「左闭右闭区间 [left, right]」来定义搜索范围初始化指针left 0数组起始下标right len(nums)-1数组末尾下标循环搜索只要 left ≤ right区间有效就执行计算中间下标mid left (right - left)/2避免 leftright 溢出比较 nums[mid] 和 target若 nums[mid] target → 找到目标返回 mid若 nums[mid] target → 目标在右半区更新 left mid 1若 nums[mid] target → 目标在左半区更新 right mid - 1循环结束未找到返回 -1。为什么用mid left (right-left)/2而不是(leftright)/2→ 避免 leftright 超出int范围比如left和right都是很大的数时相加会溢出。left (right - left)/2 (2*left right - left)/2 (left right)/2用 mid left (right-left)/2 而不是 (leftright)/2是为了避免整数溢出因为如果 left 和 right 都是接近 int 最大值的大数两者相加会超出 int 的取值范围导致数值溢出变成负数计算出错误的 mid而 left (right-left)/2 先做减法再做加法不会触发溢出且数学结果和前者完全一致。闭区间 [left, right] 意味着→ 当 nums[mid] target 时mid 肯定不是目标所以 left 要跳到 mid1→ 当 nums[mid] target 时right 要跳到 mid-1。代码实现Gopackagemainimport(fmt)// search 二分查找核心函数闭区间 [left, right] 写法// 参数// nums: 升序无重复的整型数组// target: 要查找的目标值// 返回值// 找到则返回目标值下标否则返回-1funcsearch(nums[]int,targetint)int{// 1. 初始化左右指针定义闭区间 [left, right]left:0right:len(nums)-1// 2. 循环只要区间有效left right就继续搜索forleftright{// 计算中间下标避免 leftright 溢出mid:left(right-left)/2// 3. 比较中间值和目标值ifnums[mid]target{returnmid// 找到目标直接返回下标}elseifnums[mid]target{// 目标在右半区缩小左边界到 mid1mid已排除leftmid1}else{// 目标在左半区缩小右边界到 mid-1mid已排除rightmid-1}}// 4. 循环结束未找到返回-1return-1}funcmain(){// 示例1输入nums1:[]int{-1,0,3,5,9,12}target1:9// 示例2输入nums2:[]int{-1,0,3,5,9,12}target2:2// 调用函数并输出结果fmt.Printf(示例1nums%v, target%d → 输出%d\n,nums1,target1,search(nums1,target1))// 输出4fmt.Printf(示例2nums%v, target%d → 输出%d\n,nums2,target2,search(nums2,target2))// 输出-1}时间复杂度O(log n)每次循环搜索范围缩小一半最多循环 log₂n 次比如n10000时仅需约14次循环空间复杂度O(1)仅使用left、right、mid三个变量无额外空间开销。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 10^5-10^9 nums[i] 10^9nums 是一个非递减数组-10^9 target 10^9思路两次二分找边界题目要求O(log n)复杂度因此不能遍历数组必须用二分找左边界找到第一个等于target的下标即使有重复也要最左边的找右边界找到最后一个等于target的下标即使有重复也要最右边的若左边界不存在返回-1则直接返回[-1,-1]否则返回[左边界, 右边界]。关键如何用二分找左/右边界依然用「闭区间 [left, right]」写法仅调整边界更新规则1. 找左边界的规则当nums[mid] target不直接返回而是缩小右边界right mid - 1继续往左找更早的目标值当nums[mid] target左边界右移left mid 1当nums[mid] target右边界左移right mid - 1循环结束后需验证left是否越界且nums[left] target避免目标值不存在。2. 找右边界的规则当nums[mid] target不直接返回而是扩大左边界left mid 1继续往右找更晚的目标值当nums[mid] target左边界右移left mid 1当nums[mid] target右边界左移right mid - 1循环结束后需验证right是否越界且nums[right] target避免目标值不存在。验证 left/right 是否越界主要是两个目的避免数组下标越界报错比如 left 超过数组长度、right 为负数确认目标值真的存在于数组中比如 left 在范围内但 nums [left] 不是目标值说明目标值不存在这一步是二分找边界的关键不验证的话代码会在目标值不存在时崩溃或返回错误结果。边界处理数组为空时直接返回[-1,-1]避免数组越界溢出优化mid计算用left (right-left)/2体现细节严谨性逻辑清晰拆分「找左边界」和「找右边界」两个函数代码可读性高。总结这道题的核心是「两次二分查找」分别找左/右边界区别仅在于「找到目标值后是否继续收缩边界」找左边界找到target后rightmid-1往左找找右边界找到target后leftmid1往右找代码实现Gopackagemainimport(fmt)// searchRange 查找目标值在非递减数组中的起始和结束位置// 核心思路// 1. 先找左边界第一个等于target的下标若左边界不存在直接返回[-1,-1]因为非递减右边界肯定不存在// 2. 左边界存在则找右边界最后一个等于target的下标利用非递减特性右边界必存在funcsearchRange(nums[]int,targetint)[]int{// 第一步找左边界第一个等于target的元素下标leftIdx:findLeftBound(nums,target)// 关键判断左边界为-1 → 数组中无target直接返回[-1,-1]// 依据非递减数组中等于target的元素必然连续左边界不存在则整体不存在ifleftIdx-1{return[]int{-1,-1}}// 第二步找右边界最后一个等于target的元素下标// 此时左边界存在非递减特性保证右边界必存在无需额外判断rightIdx:findRightBound(nums,target)// 只有leftIdx≠-1时才会执行而 leftIdx ! -1 意味着数组中至少有一个元素等于 targetreturn[]int{leftIdx,rightIdx}}// findLeftBound 二分查找目标值的左边界第一个等于target的下标// 参数//// nums: 非递减排列的整数数组// target: 要查找的目标值//// 返回值//// 找到则返回第一个等于target的下标否则返回-1funcfindLeftBound(nums[]int,targetint)int{left:0right:len(nums)-1leftBound:-1// 左边界默认值-1表示不存在forleftright{// 计算中间下标用left (right-left)/2 而非 (leftright)/2避免整数溢出mid:left(right-left)/2ifnums[mid]target{// 找到target先记录当前下标可能是左边界继续往左收缩找更早的元素leftBoundmid rightmid-1// 核心操作缩小右边界向左探索更早的target}elseifnums[mid]target{// target在右半区左指针右移缩小搜索范围到[mid1, right]leftmid1}else{// target在左半区右指针左移缩小搜索范围到[left, mid-1]rightmid-1}}returnleftBound// 未找到则返回初始值-1}// findRightBound 二分查找目标值的右边界最后一个等于target的下标// 参数//// nums: 非递减排列的整数数组// target: 要查找的目标值//// 返回值//// 找到则返回最后一个等于target的下标否则返回-1funcfindRightBound(nums[]int,targetint)int{left:0right:len(nums)-1rightBound:-1// 右边界默认值-1表示不存在// 闭区间[left, right]循环查找直到区间无效left rightforleftright{// 计算中间下标避免整数溢出的标准写法mid:left(right-left)/2ifnums[mid]target{// 找到target先记录当前下标可能是右边界继续往右收缩找更晚的元素rightBoundmid leftmid1// 核心操作扩大左边界向右探索更晚的target与左边界唯一区别}elseifnums[mid]target{// target在右半区左指针右移缩小搜索范围到[mid1, right]leftmid1}else{// target在左半区右指针左移缩小搜索范围到[left, mid-1]rightmid-1}}returnrightBound// 未找到则返回初始值-1}funcmain(){// 示例1target存在且有多个重复nums1:[]int{5,7,7,8,8,10}target1:8// 示例2target不存在nums2:[]int{5,7,7,8,8,10}target2:6// 示例3空数组nums3:[]int{}target3:0// 输出结果验证fmt.Printf(示例1nums%v, target%d → 输出%v\n,nums1,target1,searchRange(nums1,target1))// 预期[3,4]fmt.Printf(示例2nums%v, target%d → 输出%v\n,nums2,target2,searchRange(nums2,target2))// 预期[-1,-1]fmt.Printf(示例3nums%v, target%d → 输出%v\n,nums3,target3,searchRange(nums3,target3))// 预期[-1,-1]}// fmt.Println(searchRange(nums3, target3)) // 输出[-1 -1]时间复杂度O(log n)两次二分查找每次都是O(log n)总复杂度仍为O(log n)空间复杂度O(1)仅使用常数个变量无额外空间开销。找左边界时每次找到 target 后不直接返回而是将右边界收缩到 mid-1继续向左探索更早的 target直到循环结束最后记录的 leftBound 就是第一个最左的 target 下标找右边界时每次找到 target 后将左边界扩大到 mid1继续向右探索更晚的 target循环结束后记录的 rightBound 就是最后一个最右的 target 下标核心是「找到后不终止继续向目标方向收缩边界」这也是二分找左右边界和普通二分的核心区别。