《算法题讲解指南：优选算法-二分查找》--19.x的平方根，20.搜索插入位置

🔥小叶-duck：个人主页

❄️个人专栏：《Data-Structure-Learning》

《C++入门到进阶&自我学习过程记录》《算法题讲解指南》--从优选到贪心

✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游

目录

19. x的平方根

题目链接：

题目描述：

题目示例：

解法（二分查找算法）：

算法思路：

C++算法代码：

算法总结及流程解析：

20. 搜索插入位置

题目链接：

题目描述：

题目示例：

解法（二分查找算法）：

算法思路：

C++算法代码：

算法总结及流程解析：

结束语

19. x的平方根

题目链接：

69. x 的平方根 - 力扣（LeetCode）

题目描述：

题目示例：

解法（二分查找算法）：

算法思路：

设 x 的平方根的最终结果为 index：

分析 index 左右两边数据的特点：

• 【0，index】 之间的元素，平方之后都小于等于 x；
• 【index+1，x】之间的元素，平方之后都大于 x；

因此可以使用二分查找算法

C++算法代码：

class Solution { public: int mySqrt(int x) { int left = 0; int right = x; while(left < right) { int mid = left + ((long long)right - left + 1) / 2; //当right=INT_MAX时，则right - left + 1 = INT_MAX + 1而超出int最大值 //所以需要强转成long long类型 if((long long)mid * mid <= x) { left = mid; } else { right = mid - 1; } } return left; } };

算法总结及流程解析：

20. 搜索插入位置

题目链接：

35. 搜索插入位置 - 力扣（LeetCode）

题目描述：

题目示例：

解法（二分查找算法）：

算法思路：

      分析插入位置左右两侧区间上元素的特点：设插入位置的坐标为 index

• 【left，index-1】 内所有元素均是小于 target 的；
• 【index，right】内所有元素均是大于等于 target 的

设 left 为本轮查询的左边界，right 为本轮查询的右边界，根据 mid 位置元素的信息，分析下一轮查询的区间：

• 当 nums[ mid ] >= target 时，说明 mid 落在了 [ index, right ] 区间上，mid 左边包括 mid 本身，可能是最终结果，所以我们接下来查找的区间在 [ eft, mid ] 上。因此新 right 到 mid 位置，继续查找。
• 当 nums[ mid ] < target 时，说明 mid 落在了 [ left, index - 1 ] 区间上，mid 右边但不包括 mid 本⾝，可能是最终结果，所以我们接下来查找的区间在 [ mid+ 1, right ] 上。因此，更新 left 到 mid + 1 的位置，继续查找。

直到我们的查找区间的长度变为 1 ，也就是 left == right 的时候， left 或者 right 所在的位置就是我们要找的结果。

C++算法代码：

class Solution { public: int searchInsert(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; while(left < right) { int mid = left + (right - left) / 2; if(nums[mid] >= target) { right = mid; } else { left = mid + 1; } } if(target > nums[nums.size() - 1]) //无大于等于target的区间，需要另外处理 { return left + 1; } return left; } };

算法总结及流程解析：

结束语

      到此，19.x的平方根，20.搜索插入位置 这两道算法题就讲解完了。19.x的平方根 通过二分法确定满足条件的最大整数解，注意处理大数越界问题；20.搜索插入位置 分析目标值在有序数组中的可能位置特征，使用二分查找确定插入点，需特别处理目标值大于所有元素的情况。希望大家能有所收获！