【优选算法必刷100题】第019~20题（二分查找算法）：x 的平方根、搜索插入位置

艾莉丝努力练剑

发布于 2025-11-17 09:35:31

1500

文章被收录于专栏：C / C++C / C++

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;
    }
};