【优选算法必刷100题】第019~20题（二分查找算法）：x 的平方根、搜索插入位置
🔥艾莉丝努力练剑：个人主页
❄专栏传送门：《C语言》、《数据结构与算法》、C/C++干货分享&学习过程记录、Linux操作系统编程详解、笔试/面试常见算法：从基础到进阶
⭐️为天地立心，为生民立命，为往圣继绝学，为万世开太平
🎬艾莉丝的简介：
🎬艾莉丝的算法专栏简介：
目录
019 x 的平方根
力扣链接：69. x 的平方根
力扣题解链接：二分查找算法模版解决【x 的平方根 】问题
题目描述：
1.1 思路一：暴力解法
1.1.1 算法思路
依次枚举 [0，x] 之间的所有数 (这里没有必要研究是否枚举到x / 2还是x / 2 + 1。因为我们找到结果之后直接就返回了，往后的情况就不会判断。反而研究枚举区间，既耽误时间，又可能出错)：
（1）如果i * i == x，直接返回；
（2）如果i * i > x，说明之前的一个数是结果，返回i - 1。
由于i * i可能超过int的最大值，因此使用 long long类型。
1.1.2 算法实现
代码演示如下——
class Solution { public: int mySqrt(int x) { // 由于两个较⼤的数相乘可能会超过 int 最⼤范围 // 因此⽤ long long long long i = 0; for (i = 0; i <= x; i++) { // 如果两个数相乘正好等于 x，直接返回 i if (i * i == x) return i; // 如果第⼀次出现两个数相乘⼤于 x，说明结果是前⼀个数 if (i * i > x) return i - 1; } // 为了处理oj题需要控制所有路径都有返回值 return -1; } };时间复杂度：O(n)，空间复杂度：O(1)。
1.2 思路二：二分查找
1.2.1 算法思路
设x的平方根的最终结果为index——
1、分析index左右两次数据的特点：
（1）[ 0 , index ] 之间的元素，平方之后都是小于等于x的；
（2）[ index + 1 , x] 之间的元素，平方之后都是大于的。
因此可以使用二分查找算法。
1.2.2 算法实现
代码演示如下——
class Solution { public: int mySqrt(int x) { if(x < 1) return 0; // 处理边界情况 int left = 1,right = x; while(left < right) { long long mid = left + (right - left + 1) / 2; // 数据量大，类型改成long long更加合适，防溢出 if(mid * mid <= x) left = mid; else right = mid - 1; } return left; } };时间复杂度：O(logn)，空间复杂度：O(1)。
1.3 博主手记
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己能够推导很重要！
020 搜索插入位置
力扣链接：35. 搜索插入位置
力扣题解链接：二分查找模版解决【搜索插入位置】问题
题目描述：
2.1 算法思路——二分查找
1、分析插入位置左右两侧区间上元素的特点——
设插入位置的坐标为index，根据插入位置的特点可以知道：
（1）[left，index-1]内的所有元素均是小于target的；
（2）[index，right]内的所有元素均是大于等于target的。
2、设 left 为本轮查询的左边界，right为本轮查询的右边界。根据mid位置元素的信息，分析下一轮查询的区间：
（1）当nums[mid] >= target时，说明mid落在了[index , right]区间上，mid左边包括mid本身，可能是最终结果，所以我们接下来查找的区间在[left，mid]上。因此，更新right到mid位置，继续查找；
（2）当nums[mid] < target时，说明mid落在了（[left , index - 1]区间上，mid右边但不包括mid本身，可能是最终结果，所以我们接下来查找的区间在[mid + 1 , right]上。因此，更新[left到mid+1的位置，继续查找。
3、到我们的查找区间的长度变为1，也就是left == right的时候，left 或者 right 所在的位置就是我们要找的结果。
2.2 算法实现
代码演示如下——
class Solution { public: int searchInsert(vector<int>& nums, int target) { int left = 0,right = nums.size() - 1; while(left < right) { int mid = left + (right - left) / 2; if(nums[mid] < target) left = mid + 1; else right = mid; } if(nums[left] < target) return left + 1; else return left; } };left和right这里已经相遇了，返回left或者right都是可以的——
class Solution { public: int searchInsert(vector<int>& nums, int target) { int left = 0,right = nums.size() - 1; while(left < right) { int mid = left + (right - left) / 2; if(nums[mid] < target) left = mid + 1; else right = mid; } if(nums[right] < target) return right + 1; else return right; } };时间复杂度：O(logn)，空间复杂度：O(1)
2.3 博主手记
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己能够推导很重要！
结尾
往期回顾：
【优选算法必刷100题】第018题（二分查找算法）：在排序数组中查找元素的第一个和最后一个位置
结语：都看到这里啦！请大佬不要忘记给博主来个“一键四连”哦！
🗡博主在这里放了一只小狗，大家看完了摸摸小狗放松一下吧！🗡
૮₍ ˶ ˊ ᴥ ˋ˶₎ა
