LeetCode算法日记 - Day 10: x 的平方根、搜索插入位置
目录
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] <= 104nums为 无重复元素 的 升序 排列数组-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;}
}