【算法】搜索插入位置 x的平方根

算法场景

二分查找作为一种高效的查找算法，时间复杂度为O ( l o g n ) O(logn)O(logn)
，以下结合此文的「搜索插入位置」和「平方根求解」，来体验它的高效！

一、搜索插入位置

1.1 题目链接

LeetCode_35搜索插入位置【点击进入】

1.2 题目描述

给定一个无重复元素的升序排列数组nums和一个目标值target，在数组中找到目标值并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。要求必须使用时间复杂度为O(log n)的算法。

1.3 题目示例

• 示例 1：
  输入: nums = [1,3,5,6], target = 5
  输出: 2
• 示例 2：
  输入: nums = [1,3,5,6], target = 2
  输出: 1
• 示例 3：
  输入: nums = [1,3,5,6], target = 7
  输出: 4

1.4 算法思路

本题的核心是利用二分查找高效定位目标值的位置或插入点，关键在于把握「升序数组」的特性和边界条件的处理：

1. 初始化搜索区间：左边界left = 0，右边界right = nums.size() - 1，覆盖整个数组范围。
2. 二分查找核心循环：当left < right时，计算中间位置mid = left + (right - left) / 2（该写法可避免left + right溢出）。
   • 若nums[mid] < target：说明目标值在mid右侧，将左边界更新为mid + 1。
   • 否则：说明目标值在mid左侧或等于nums[mid]，将右边界更新为mid。
3. 循环结束后，left与right重合，此时需判断最终位置：
   • 若nums[left] < target：说明目标值大于数组所有元素，应插入到数组末尾，返回right + 1。
   • 否则：目标值的位置或插入点即为right（与left相等）。

1.5 核心代码

classSolution{public:intsearchInsert(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<right){intmid=left+(right-left)/2;if(nums[mid]<target)left=mid+1;elseright=mid;}if(nums[left]<target)returnright+1;returnright;}};

1.6 示例测试（总代码）

#include<iostream>#include<vector>usingnamespacestd;classSolution{public:intsearchInsert(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<right){intmid=left+(right-left)/2;if(nums[mid]<target)left=mid+1;elseright=mid;}if(nums[left]<target)returnright+1;returnright;}};intmain(){// 示例 1 测试vector<int>nums1={1,3,5,6};inttarget1=5;Solution sol;cout<<"示例 1 输出："<<sol.searchInsert(nums1,target1)<<endl;// 预期输出 2// 示例 2 测试vector<int>nums2={1,3,5,6};inttarget2=2;cout<<"示例 2 输出："<<sol.searchInsert(nums2,target2)<<endl;// 预期输出 1// 示例 3 测试vector<int>nums3={1,3,5,6};inttarget3=7;cout<<"示例 3 输出："<<sol.searchInsert(nums3,target3)<<endl;// 预期输出 4return0;}

二、x 的平方根

2.1 题目链接

LeetCode_60x的平方根【点击进入】

2.2 题目描述

给你一个非负整数x，计算并返回x的算术平方根。由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。注意：不允许使用任何内置指数函数和算符（如pow(x, 0.5)或x ** 0.5）。

2.3 题目示例

• 示例 1：
  输入：x = 4
  输出：2
• 示例 2：
  输入：x = 8
  输出：2
  解释：8 的算术平方根是 2.82842…，小数部分舍去后返回 2。

2.4 算法思路

本题本质是在「0 到 x」的整数区间内，查找最大的整数mid使得mid * mid <= x，同样适用二分查找，需重点处理边界和溢出问题：

1. 边界情况处理：当x < 1时（即 x = 0），直接返回 0。
2. 初始化搜索区间：左边界left = 0，右边界right = x（因为对于非负整数 x，其平方根一定不大于 x）。
3. 二分查找核心循环：当left < right时，计算中间位置mid = left + (right - left + 1LL) / 2：
   • 加1LL是为了避免「死循环」：当区间收缩到[left, left+1]时，确保能正确移动左边界。
   • 用long long类型存储mid：防止mid * mid超出 int 范围导致溢出。
4. 区间更新逻辑：
   • 若mid * mid <= x：说明mid可能是答案或答案在mid右侧，将左边界更新为mid。
   • 否则：说明答案在mid左侧，将右边界更新为mid - 1。
5. 循环结束后，left与right重合，即为x算术平方根的整数部分。

2.5 核心代码

classSolution{public:intmySqrt(intx){// 处理边界情况if(x<1)return0;else{intleft=0;intright=x;while(left<right){longlongmid=left+(right-left+1LL)/2;// 溢出处理if(mid*mid<=x)left=mid;elseright=mid-1;}returnleft;}}};

2.6 示例测试（总代码）

#include<iostream>usingnamespacestd;classSolution{public:intmySqrt(intx){// 处理边界情况if(x<1)return0;else{intleft=0;intright=x;while(left<right){longlongmid=left+(right-left+1LL)/2;// 溢出处理if(mid*mid<=x)left=mid;elseright=mid-1;}returnleft;}}};intmain(){// 示例 1 测试intx1=4;Solution sol;cout<<"示例 1 输出："<<sol.mySqrt(x1)<<endl;// 预期输出 2// 示例 2 测试intx2=8;cout<<"示例 2 输出："<<sol.mySqrt(x2)<<endl;// 预期输出 2// 额外测试用例intx3=0;cout<<"x=0 输出："<<sol.mySqrt(x3)<<endl;// 预期输出 0intx4=5;cout<<"x=5 输出："<<sol.mySqrt(x4)<<endl;// 预期输出 2intx5=9;cout<<"x=9 输出："<<sol.mySqrt(x5)<<endl;// 预期输出 3return0;}

总结

在本篇文章中，我们通过「搜索插入位置」与「x 的平方根」两个经典题目，深入理解了二分查找的核心思想与应用方式。

二分查找的核心价值在于将线性搜索的O(n)时间复杂度优化为O(log n)，尤其适用于「有序区间」的查找问题。通过两道题的对比可以发现：

• 二分查找的关键在于「确定搜索区间」和「区间更新规则」，需根据题目目标灵活调整（如查找目标值 vs 查找最大满足条件值）；
• 边界处理（如数组为空、x=0 等极端情况）和溢出防护（如用 long long 存储中间值）是二分查找实现的常见考点；
• 虽然两道题的场景不同，但都利用了「有序性」和「区间收缩」的核心逻辑，体现了二分查找的通用性。

掌握二分查找的本质后，面对有序数组查找、数值逼近等问题时，都可以快速构建解题思路，高效解决问题。