收录网站排名重庆高考征集志愿网站

收录网站排名,重庆高考征集志愿网站,文案类的网站,做相册的网站dw二分查找是高效解决有序/局部有序数组问题的经典算法#xff0c;核心思想是通过不断缩小“可能包含目标的区间”#xff0c;将时间复杂度从暴力遍历的 O(n)O(n)O(n) 优化到 O(log⁡n)O(\log n)O(logn)。 它的适用场景非常广泛#xff1a;不仅能解决“查找目标值”这类基础问…二分查找是高效解决有序/局部有序数组问题的经典算法核心思想是通过不断缩小“可能包含目标的区间”将时间复杂度从暴力遍历的O(n)O(n)O(n)优化到O(log⁡n)O(\log n)O(logn)。它的适用场景非常广泛不仅能解决“查找目标值”这类基础问题还能处理“找边界”“找极值”“旋转数组”等复杂场景。本文将通过7道经典题目拆解二分查找在不同场景下的解题思路与代码实现。一、在排序数组中查找元素的第一个和最后一个位置题目描述给定非递减排序的整数数组nums和目标值target找出target在数组中的开始位置和结束位置若不存在则返回[-1, -1]。要求时间复杂度为O(log⁡n)O(\log n)O(logn)。示例输入nums [5,7,7,8,8,10], target 8输出[3,4]输入nums [5,7,7,8,8,10], target 6输出[-1,-1]解题思路通过两次二分查找分别确定左边界和右边界找左边界二分找第一个等于target的位置。若nums[mid] target左指针右移否则右指针左移最终左指针即为左边界。找右边界二分找最后一个等于target的位置。若nums[mid] target左指针右移否则右指针左移最终右指针即为右边界。若左边界对应的元素不是target直接返回[-1,-1]。完整代码classSolution{public:vectorintsearchRange(vectorintnums,inttarget){if(nums.size()0)return{-1,-1};intbegin0;intleft0,rightnums.size()-1;// 找左边界while(leftright){intmidleft(right-left)/2;if(nums[mid]target)leftmid1;elserightmid;}if(nums[left]!target)return{-1,-1};elsebeginleft;// 找右边界rightnums.size()-1;while(leftright){intmidleft(right-left1)/2;if(nums[mid]target)leftmid;elserightmid-1;}return{begin,right};}};复杂度分析时间复杂度O(log⁡n)O(\log n)O(logn)两次二分查找各占O(log⁡n)O(\log n)O(logn)。空间复杂度O(1)O(1)O(1)仅用常数级额外变量。二、x 的平方根题目描述给定非负整数x计算并返回其算术平方根的整数部分舍去小数部分不允许使用内置指数函数或运算符。示例输入x 4输出2输入x 8输出28的平方根是2.828…取整数部分解题思路通过二分查找找最大的整数mid使得mid² x边界条件若x 1直接返回0否则二分区间为[1, x]。二分过程计算mid left (right - left 1) / 2避免死循环用long long存储mid * mid防止整数溢出若mid * mid x左指针右移保留当前候选值否则右指针左移。完整代码classSolution{public:intmySqrt(intx){if(x1)return0;intleft1,rightx;while(leftright){longlongmidleft(right-left1)/2;if(mid*midx)leftmid;elserightmid-1;}returnleft;}};复杂度分析时间复杂度O(log⁡x)O(\log x)O(logx)二分区间大小为x每次缩小一半。空间复杂度O(1)O(1)O(1)仅用常数级额外变量。三、搜索插入位置题目描述给定排序数组nums和目标值target找到target在数组中的索引若不存在则返回其按顺序插入的位置。要求时间复杂度为O(log⁡n)O(\log n)O(logn)。示例输入nums [1,3,5,6], target 5输出2输入nums [1,3,5,6], target 2输出1解题思路通过二分查找找第一个大于等于target的位置若nums[mid] target说明target在右边左指针右移否则右指针左移。最终左指针即为目标位置若nums[left] target则插入到left1否则插入到left。完整代码classSolution{public:intsearchInsert(vectorintnums,inttarget){intleft0,rightnums.size()-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target)leftmid1;elserightmid;}returnnums[left]target?left1:left;}};复杂度分析时间复杂度O(log⁡n)O(\log n)O(logn)二分遍历数组。空间复杂度O(1)O(1)O(1)仅用常数级额外变量。四、山脉数组的峰顶索引题目描述给定山脉数组arr先递增后递减返回峰值元素的下标要求时间复杂度为O(log⁡n)O(\log n)O(logn)。示例输入arr [0,1,0]输出1输入arr [0,2,1,0]输出1解题思路山脉数组的峰值满足arr[mid] arr[mid-1]且arr[mid] arr[mid1]通过二分缩小范围二分区间为[1, arr.size()-2]避免越界比较arr[mid]和arr[mid-1]若arr[mid] arr[mid-1]说明峰值在右边左指针右移。否则说明峰值在左边右指针左移。最终左指针即为峰值下标。完整代码classSolution{public:intpeakIndexInMountainArray(vectorintarr){intleft1,rightarr.size()-2;while(leftright){intmidleft(right-left1)/2;if(arr[mid]arr[mid-1])leftmid;elserightmid-1;}returnleft;}};复杂度分析时间复杂度O(log⁡n)O(\log n)O(logn)二分遍历数组。空间复杂度O(1)O(1)O(1)仅用常数级额外变量。五、寻找峰值题目描述峰值元素是指严格大于左右相邻值的元素给定数组nums返回任意一个峰值的下标。假设nums[-1] nums[n] -∞要求时间复杂度为O(log⁡n)O(\log n)O(logn)。示例输入nums [1,2,3,1]输出2输入nums [1,2,1,3,5,6,4]输出1或5解题思路利用“边界为负无穷”的假设通过二分找峰值二分区间为[0, nums.size()-1]比较nums[mid]和nums[mid1]若nums[mid] nums[mid1]说明峰值在左边包括mid右指针左移。否则说明峰值在右边左指针右移。最终左指针即为峰值下标必然存在峰值。完整代码classSolution{public:intfindPeakElement(vectorintnums){intleft0,rightnums.size()-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]nums[mid1])rightmid;elseleftmid1;}returnleft;}};复杂度分析时间复杂度O(log⁡n)O(\log n)O(logn)二分遍历数组。空间复杂度O(1)O(1)O(1)仅用常数级额外变量。六、寻找旋转排序数组中的最小值题目描述给定升序旋转后的数组nums元素互不相同返回数组中的最小元素要求时间复杂度为O(log⁡n)O(\log n)O(logn)。示例输入nums [3,4,5,1,2]输出1输入nums [4,5,6,7,0,1,2]输出0解题思路旋转后的数组分为“左升序段”和“右升序段”最小值是右段的第一个元素二分区间为[0, nums.size()-1]比较nums[mid]和nums.back()最后一个元素若nums[mid] nums.back()说明mid在左段最小值在右边左指针右移。否则说明mid在右段最小值在左边包括mid右指针左移。最终左指针即为最小值的下标。完整代码classSolution{public:intfindMin(vectorintnums){intleft0,rightnums.size()-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]nums[nums.size()-1])leftmid1;elserightmid;}returnnums[left];}};复杂度分析时间复杂度O(log⁡n)O(\log n)O(logn)二分遍历数组。空间复杂度O(1)O(1)O(1)仅用常数级额外变量。七、点名题目描述班级n位同学的学号为0~n-1点名结果记录于升序数组records仅一位同学缺席返回其学号。示例输入records [0,1,2,3,5]输出4输入records [0,1,2,3,4,5,6,8]输出7解题思路正常情况下records[mid] mid缺席的学号会打破该关系二分区间为[0, records.size()-1]比较records[mid]和mid若records[mid] mid说明缺席在右边左指针右移。否则说明缺席在左边包括mid右指针左移。最终若records[left] left缺席学号为left1否则为left。完整代码classSolution{public:inttakeAttendance(vectorintrecords){intleft0,rightrecords.size()-1;while(leftright){intmidleft(right-left)/2;if(records[mid]mid)leftmid1;elserightmid;}returnrecords[left]left?left1:left;}};复杂度分析时间复杂度O(log⁡n)O(\log n)O(logn)二分遍历数组。空间复杂度O(1)O(1)O(1)仅用常数级额外变量。