目录

1.  x 的平方根

1.1 题目解析

1.2 解法

1.3 代码实现

2. 搜索插入位置

2.1 题目解析

2.2 解法

2.3 代码实现

---

1.  x 的平方根

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

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

• 0 <= x <= 231 - 1

1.1 题目解析

本题要求计算非负整数 x 的算术平方根，保留整数部分（向下取整），不能使用内置开方或指数函数。我们要找的是最大整数 r，满足：r * r <= x，这意味着答案是一个边界值，左边（含自身）的平方小于等于 x，右边的平方大于 x。。

i）区间特性

• [0, r] 之间的数平方后 ≤ x

• [r + 1, x] 之间的数平方后 > x ，这样的区间特性非常适合用二分查找来锁定边界

ii）据范围与溢出

在计算平方时可能会超出 32 位整数范围，因此需要使用更大的数据类型（如 long 或 long long）来存储中间结果。

1.2 解法

i）初始化左右边界：left = 0, right = x

ii）循环执行：

• 取中点：mid = left + (right - left+1) / 2

• 如果 mid * mid <= x：
  说明 mid 可能是结果，但右边可能还有更大的满足条件的值 → 更新：left = mid 

• 否则（mid * mid > x）：
  说明 mid 太大，答案一定在左半部分 → 更新：right = mid - 1

1.3 代码实现

class Solution {
    public int mySqrt(int x) {
        if(x<1){return 0;}
        long left = 0,right = x;
        while(left<right){
            long mid = left + (right-left+1)/2;
            if(mid*mid<=x){
                left = mid;
            }else{
                right = mid -1;
            }
        }
        return (int)left;
    }
}

2. 搜索插入位置

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

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 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 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 为 无重复元素 的 升序 排列数组
• -104 <= target <= 104

2.1 题目解析

本题要求在一个升序排序的数组中找到目标值 target 的索引，如果不存在则返回它应该被插入的位置。题目明确要求时间复杂度为 O(log n)，这意味着要用 二分查找 来完成。

通过分析可得：

i）插入位置的定义
插入位置 index 满足：

• 在位置 index 之前的所有元素都 小于 target

• 从位置 index 开始的所有元素都 大于等于 target
  换句话说，index 就是第一个大于等于 target 的元素的下标。

ii)为什么判断条件是 nums[mid] >= target

• 如果 nums[mid] >= target，说明 mid 以及它左边的部分可能包含插入位置，因此需要继续在左半区间搜索。

• 如果 nums[mid] < target，则可以排除 mid 及其左侧，继续在右半区间搜索。

• 这道题的关键点在于：第一个大于等于 target 的值可以确定位置，但第一个小于 target 的值不能确定位置，因此判断条件必须用 >=。

iii)终止条件
二分查找不断缩小 [left, right] 的范围，直到 left == right，此时 left（或 right）就是插入位置

iiii）边界情况

• 如果 target 比所有元素都小，返回 0。

• 如果 target 比所有元素都大，返回 nums.length。

• 如果数组中存在 target，直接返回它的第一个出现位置。

2.2 解法

i）区间特性
设插入位置为 index，则：

• [left, index - 1] 内的所有元素 < target

• [index, right] 内的所有元素 ≥ targe

这道题的判断依据是，第一个大于 t 的值可以确定位置，但是第一个小的值不可以确定 t 的位置，所以判断条件式 mid>= t

ii）判断条件的核心原因
这道题的判断依据是：第一个大于等于 target 的值可以确定位置，但是第一个小于 target 的值不能确定位置，因为小于 target 的值后面可能还会出现等于 target 的元素。。

iii）二分查找步骤

• 初始化：left = 0，right = nums.length - 1

• 计算中点：mid = left + (right - left) / 2

  • 如果nums[mid] >= target：
    说明 mid 落在 [index, right] 区间，mid 以及它左边可能是答案
    → 更新 right = mid

  • 如果 nums[mid] < target：
    说明 mid 落在 [left, index - 1] 区间，答案在右半区间
    → 更新 left = mid + 1

• 循环直到 left == right，此时 left（或 right）就是插入位置。

2.3 代码实现

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0,right = nums.length-1;
        while(left<right){
            int mid = left + (right-left)/2;
            if(nums[mid]>=target){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        if(nums[left]<target){
            return left+1;
        }
        return left;
    }
}