LeetCode Hot 100 | 二分查找C 题解目录LeetCode Hot 100 | 二分查找C 题解前言1. 35. 搜索插入位置 题目描述解题思路复杂度分析C 代码2. 74. 搜索二维矩阵 题目描述解题思路复杂度分析C 代码3. 34. 在排序数组中查找元素的第一个和最后一个位置 题目描述解题思路复杂度分析C 代码4. 33. 搜索旋转排序数组 题目描述解题思路复杂度分析C 代码总结前言二分查找通过每次将搜索范围减半将 O(n) 的线性查找优化为 O(log n)。本篇涵盖从基础的插入位置、旋转数组查找到在矩阵中二分查找的四道经典题目重点掌握左右边界的更新策略。1. 35. 搜索插入位置 题目描述给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。请必须使用时间复杂度为O(log n)的算法。示例 1输入: nums [1,3,5,6], target 5 输出: 2示例 2输入: nums [1,3,5,6], target 2 输出: 1约束1 nums.length 10^4-10^4 nums[i] 10^4nums 无重复元素且升序排列解题思路标准二分查找找不到时left即为插入位置此时left rightleft正好是第一个大于 target 的位置。以nums [1,3,5,6], target 2为例迭代leftrightmidnums[mid]操作10313target 3, right020001target 1, left1结束10--left right, 返回 left1复杂度分析时间O(log n)空间O(1)C 代码classSolution{public:intsearchInsert(vectorintnums,inttarget){intleft0;intrightnums.size()-1;while(leftright){intmid(leftright)/2;if(targetnums[mid]){leftmid1;}elseif(targetnums[mid]){rightmid-1;}else{returnmid;}}returnleft;}};2. 74. 搜索二维矩阵 题目描述给你一个满足下述两条属性的m x n整数矩阵每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。给你一个整数target如果target在矩阵中返回true否则返回false。示例 1输入matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target 3 输出true示例 2输入matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target 13 输出false约束m matrix.length,n matrix[i].length1 m, n 100,-10^4 matrix[i][j], target 10^4解题思路从矩阵右上角出发若当前值大于 target则列左移若小于 target则行下移等于则返回 true。本质是 Z 字形搜索。以matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target 3为例步骤rowclommatrix值操作10377 3, clom–20255 3, clom–3013 3, 返回 true复杂度分析时间O(m n)空间O(1)C 代码classSolution{public:boolsearchMatrix(vectorvectorintmatrix,inttarget){intmaxRowmatrix.size()-1;intmaxClommatrix[0].size()-1;introw0;intclommaxClom;while(rowmaxRowclom0){if(matrix[row][clom]target){clom--;}elseif(matrix[row][clom]target){row;}else{returntrue;}}returnfalse;}};3. 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]约束0 nums.length 10^5,-10^9 nums[i] 10^9解题思路二分查找两次isLefttrue找左边界命中后 rightmid-1 继续向左isLeftfalse找右边界命中后 leftmid1 继续向右。以nums [5,7,7,8,8,10], target 8查找左边界为例迭代leftrightmidnums[mid]操作105277 8, left323548 8, index4, right333338 8, index3, right2结束返回 index3复杂度分析时间O(log n)空间O(1)C 代码classSolution{public:vectorintsearchRange(vectorintnums,inttarget){intleftbinSearch(nums,target,true);intrightbinSearch(nums,target,false);return{left,right};}intbinSearch(vectorintnums,inttarget,boolisLeft){intleft0;intrightnums.size()-1;intindex-1;while(leftright){intmid(leftright)/2;if(targetnums[mid]){leftmid1;}elseif(targetnums[mid]){rightmid-1;}else{indexmid;if(isLeft){rightmid-1;}else{leftmid1;}}}returnindex;}};4. 33. 搜索旋转排序数组 题目描述整数数组nums按升序排列数组中的值互不相同。在传递给函数之前nums在预先未知的某个下标k上进行了旋转。给你旋转后的数组nums和一个整数target如果nums中存在这个目标值target则返回它的下标否则返回-1。示例 1输入nums [4,5,6,7,0,1,2], target 0 输出4示例 2输入nums [4,5,6,7,0,1,2], target 3 输出-1约束1 nums.length 5000,-10^4 nums[i] 10^4解题思路旋转后的数组二分后必有一半是有序的。判断左半是否有序nums[left] nums[mid]若 target 在有序一半内则缩小范围否则去另一半。以nums [4,5,6,7,0,1,2], target 0为例迭代leftrightmidnums[mid]左半有序target在左半操作106374≤7 ✓0∈[4,7)? 否left4246510≤1 ✓0∈[0,1)? 是right434440 target返回 4复杂度分析时间O(log n)空间O(1)C 代码classSolution{public:intsearch(vectorintnums,inttarget){intleft0;intrightnums.size()-1;while(leftright){intmid(leftright)/2;if(nums[mid]target)returnmid;if(nums[left]nums[mid]){if(nums[left]targettargetnums[mid]){rightmid-1;}else{leftmid1;}}else{if(targetnums[mid]nums[right]target){leftmid1;}else{rightmid-1;}}}return-1;}};总结题号题目难度核心技巧时间复杂度35搜索插入位置简单标准二分left即插入位置O(log n)74搜索二维矩阵中等右上角 Z 字形搜索O(mn)34查找第一个和最后一个位置中等二分两次isLeft控制边界方向O(log n)33搜索旋转排序数组中等判断有序半段后缩小范围O(log n)