leetcode——二分法
基本原理
class Solution {
public int search(int[] nums, int target) {
// 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
if (target < nums[0] || target > nums[nums.length - 1]) {
return -1;
}
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target) {
return mid;
}
else if (nums[mid] < target) {
left = mid + 1;
}
else { // nums[mid] > target
right = mid - 1;
}
}
// 未找到目标值
return -1;
}
}34.在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组
nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值
target，返回[-1, -1]。你必须设计并实现时间复杂度为
O(log n)的算法解决此问题。示例 1：
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]示例 2：
输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]示例 3：
输入：nums = [], target = 0 输出：[-1,-1]提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109nums是一个非递减数组-109 <= target <= 109
原理
该问题的目标是查找目标值
target在一个已排序的非递减数组nums中的开始和结束位置。为了确保算法的时间复杂度为O(log n)，我们使用 二分查找 来实现高效的查找。解决思路：
二分查找：由于数组是排序好的，可以使用二分查找来寻找目标值
target。首先通过二分查找找到target中的一次出现位置，然后再向两边扩展，查找目标值的连续区间的起始和结束位置。左边界的寻找：当我们找到了目标值的一个位置后，向左扩展直到找到目标值的第一个出现位置。
右边界的寻找：同样地，从中间位置开始，向右扩展直到找到目标值的最后一个出现位置。
二分查找的步骤：
- 确定中间位置：通过计算
middle = left + (right - left) / 2来避免溢出，找到当前区间的中间元素。- 比较中间元素：如果
nums[middle] == target，则表示找到了目标值的位置，此时进行左右扩展查找；如果nums[middle] < target，则目标值在右半部分，调整左指针；如果nums[middle] > target，则目标值在左半部分，调整右指针。结果：当目标值存在时，返回找到的起始位置和结束位置；如果数组中没有目标值，返回
[-1, -1]。复杂度分析：
时间复杂度：
O(log n)。由于二分查找的时间复杂度为O(log n)，且扩展操作的时间复杂度最多为O(n)，但实际情况是扩展操作的次数通常较小，因此总的时间复杂度是O(log n)。空间复杂度：
O(1)。该算法只使用了常数的额外空间，除了输入数组和返回结果。
代码
class Solution {
public int[] searchRange(int[] nums, int target) {
// 左右指针初始化
int left = 0, right = nums.length - 1;
int[] ans = {-1, -1}; // 默认返回 [-1, -1]，表示目标值不在数组中
int m = 0, n = 0; // m 为目标值的开始位置，n 为目标值的结束位置
// 使用二分查找寻找目标值
while (left <= right) {
int middle = left + (right - left) / 2; // 计算中间位置
if (nums[middle] < target) {
left = middle + 1; // 目标值在右边，调整左指针
} else if (nums[middle] > target) {
right = middle - 1; // 目标值在左边，调整右指针
} else {
// 找到目标值，设置 m 和 n
m = middle;
n = middle;
// 向右扩展，找到目标值的结束位置
for (int i = middle + 1; i <= nums.length - 1; i++) {
if (nums[i] == target) {
n++; // 扩展结束位置
} else {
break; // 目标值结束，跳出循环
}
}
// 向左扩展，找到目标值的开始位置
for (int i = middle - 1; i >= 0; i--) {
if (nums[i] == target) {
m--; // 扩展开始位置
} else {
break; // 目标值开始，跳出循环
}
}
// 将找到的开始位置和结束位置返回
ans[0] = m;
ans[1] = n;
return ans; // 返回目标值的起始和结束位置
}
}
// 如果没有找到目标值，返回 [-1, -1]
return ans;
}
}
35.搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为
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
原理
该问题要求我们在一个已经排序好的数组中找到目标值
target的位置。如果目标值存在，则返回其索引；如果目标值不存在，则返回它在数组中的“插入位置”，即目标值应该插入到哪个位置才能保持数组的升序排列。为了满足题目要求的时间复杂度
O(log n)，我们使用 二分查找 来高效地找到目标值的索引或插入位置。解决思路：
二分查找：由于数组是排序好的，可以使用二分查找来查找目标值。如果目标值存在，二分查找会找到它的索引。如果目标值不存在，二分查找会找到一个插入位置，即目标值应该插入的索引。
查找目标值的过程：
- 初始化左右指针
left = 0和right = nums.length - 1。- 计算中间位置
middle = left + (right - left) / 2。使用这种方法可以避免溢出。- 如果
nums[middle] < target，说明目标值应该在右半部分，调整left = middle + 1。- 如果
nums[middle] > target，说明目标值应该在左半部分，调整right = middle - 1。- 如果
nums[middle] == target，说明找到了目标值，直接返回middle。插入位置的判断：
- 当二分查找结束后，
left指针所指的位置即为目标值的插入位置。如果目标值存在，left会指向目标值的索引；如果目标值不存在，left会指向目标值应该插入的位置。复杂度分析：
- 时间复杂度：
O(log n)。二分查找的时间复杂度是O(log n)，每次迭代都将搜索区间缩小一半，因此在最坏情况下，最多需要log n次操作。- 空间复杂度：
O(1)。该算法只使用了常数的额外空间，只使用了left、right和middle这些变量，空间复杂度是常数级别的。
代码
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;
// 使用二分查找来确定目标值的位置
while (left <= right) {
int middle = left + (right - left) / 2; // 计算中间位置，避免溢出
if (nums[middle] < target) {
left = middle + 1; // 如果中间元素小于目标值，移动左指针
} else if (nums[middle] > target) {
right = middle - 1; // 如果中间元素大于目标值，移动右指针
} else {
return middle; // 如果找到目标值，直接返回其索引
}
}
// 如果未找到目标值，返回目标值应该插入的位置
return left;
}
}
69.x的平方根
给你一个非负整数
x，计算并返回x的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如
pow(x, 0.5)或者x ** 0.5。示例 1：
输入：x = 4 输出：2示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。提示：
0 <= x <= 231 - 1
原理
该问题要求我们计算一个非负整数
x的算术平方根并返回其整数部分（即舍去小数部分）。不允许使用内置的指数函数或平方根计算函数。为了实现这一点，我们可以通过 二分查找 的方法来计算平方根。解决思路：
二分查找法：我们可以利用二分查找的方法来逼近平方根。
- 由于平方根是一个递增的函数（对于非负数），我们可以在
[0, x/2]的区间内进行查找。为了避免溢出，right的初始值设置为x / 2，而不是x本身。- 使用
left和right来确定搜索区间，每次通过middle = left + (right - left) / 2计算中间位置来进行二分查找。二分查找的过程：
- 如果
middle * middle < x，说明平方根应该更大，此时将left调整为middle + 1。- 如果
middle * middle > x，说明平方根应该更小，此时将right调整为middle - 1。- 如果
middle * middle == x，则找到了平方根，直接返回middle。- 当
middle * middle小于x且(middle + 1) * (middle + 1)大于x时，说明middle就是我们要找的整数平方根。为什么右边界是
x / 2：
- 由于当
x > 1时，平方根的最大值不会超过x / 2（比如对于x = 100，其平方根最大也只是 10，因此x / 2是一个合理的最大搜索范围）。特殊情况：
- 当
x为 0 或 1 时，直接返回x，因为它们的平方根分别是 0 和 1，不需要进行进一步的计算。复杂度分析：
- 时间复杂度：
O(log n)。每次二分查找都将搜索范围缩小一半，因此最多需要log n次操作。- 空间复杂度：
O(1)。该算法只使用了常数的额外空间，空间复杂度是常数级别的。
代码
class Solution {
public int mySqrt(int x) {
int ans = 0;
long left = 0, right = x / 2; // 初始化左指针和右指针，右指针最大值为 x / 2，避免溢出
// 如果 x 等于 0 或 1，直接返回 x，因为 0 的平方根是 0，1 的平方根是 1
if (x == 1 || x == 0) {
return x;
}
// 使用二分查找的方式来查找平方根
while (left <= right) {
// 计算中间位置
long middle = left + (right - left) / 2;
// 如果 middle 的平方小于 x，说明平方根应该更大
if ((long)(middle * middle) < (long)x) {
System.out.println("小了：" + middle);
// 如果 middle+1 的平方大于 x，则说明 middle 就是我们要找的平方根
if ((long)((middle + 1) * (middle + 1)) > (long)x) {
System.out.println("找到了：" + middle);
return (int)middle;
} else {
left = middle + 1; // 否则继续扩大范围，搜索更大的数
}
}
// 如果 middle 的平方大于 x，说明平方根应该更小
else if ((long)(middle * middle) > (long)x) {
System.out.println("大了：" + middle);
// 如果 middle-1 的平方小于或等于 x，则说明 middle-1 就是我们要找的平方根
if ((long)((middle - 1) * (middle - 1)) <= (long)x) {
System.out.println("找到了：" + (middle - 1));
return (int)(middle - 1);
} else {
right = middle - 1; // 否则继续缩小范围，搜索更小的数
}
}
// 如果 middle 的平方正好等于 x，直接返回 middle
else {
System.out.println("找到了：" + middle);
return (int)middle;
}
}
// 如果没有找到平方根，返回 0
return 0;
}
}
但是这段代码判断条件过多，有点繁琐
class Solution {
public int mySqrt(int x) {
// 初始化左指针为 0，右指针为 x / 2 + 1（对平方根的最大值的上界进行优化）
int l = 0, r = x / 2 + 1, res = -1;
// 通过二分查找的方法，寻找平方根
while (l <= r) {
// 计算中间位置 mid
int mid = l + (r - l) / 2;
// 如果 mid 的平方小于等于 x，说明平方根可能是 mid 或者更大
if ((long) mid * mid <= x) {
res = mid; // 更新 res 为 mid
l = mid + 1; // 继续搜索右半区
} else {
r = mid - 1; // 否则搜索左半区
}
}
// 返回找到的整数平方根
return res;
}
}
这是官方给的最优代码，可以看到在小于等于x的时候以及可以接触到答案了
367.有效的平方数
给你一个正整数
num。如果num是一个完全平方数，则返回true，否则返回false。完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数，如
sqrt。示例 1：
输入：num = 16 输出：true 解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。示例 2：
输入：num = 14 输出：false 解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。提示：
1 <= num <= 231 - 1
原理
该算法通过 二分查找 来确定一个正整数
num是否是一个完全平方数。完全平方数是可以表示为某个整数的平方的数，也就是说，如果num是完全平方数，那么一定存在一个整数x，使得x * x = num。详细过程：
初始条件：
- 如果
num == 1，我们直接返回true，因为1是一个完全平方数。二分查找：
- 通过二分查找的方法，我们在区间
[0, num/2]中寻找整数平方根。如果num是完全平方数，那么在这个区间内会找到一个整数x，使得x * x = num。- 左指针
left初始为 0，右指针right初始为num / 2，这是因为平方根的最大值不会超过num / 2（对于num > 1的情况）。- 在每次循环中，我们计算中间值
middle，并检查middle * middle和num的关系：
- 如果
middle * middle < num，说明平方根可能大于middle，于是我们将左指针移动到middle + 1。- 如果
middle * middle > num，说明平方根可能小于middle，于是我们将右指针移动到middle - 1。- 如果
middle * middle == num，说明找到了完全平方数，返回true。返回结果：
- 如果循环结束后没有找到完全平方数（即
left > right），我们返回false，表示num不是完全平方数。为什么要使用
(long) middle * middle：
- 因为
middle * middle可能会超出int类型的范围（尤其是当num较大时）。为了防止整数溢出，我们将middle强制转换为long类型，以确保计算不会溢出。复杂度分析：
- 时间复杂度：
O(log n)。每次迭代都会将搜索区间减半，因此最多需要log n次迭代。- 空间复杂度：
O(1)。算法只使用了常数的额外空间，空间复杂度是常数级别的。
代码
class Solution {
public boolean isPerfectSquare(int num) {
// 如果 num 为 1，直接返回 true，因为 1 是完全平方数（1 * 1 = 1）
if (num == 1) {
return true;
}
// 初始化左指针为 0，右指针为 num / 2。sqrt(num) 的最大值是 num / 2（对于 num > 1）
int left = 0, right = num / 2;
// 使用二分查找的方法，寻找 num 的平方根
while (left <= right) {
// 计算中间位置 mid
int middle = left + (right - left) / 2;
// 如果 middle 的平方小于 num，说明平方根可能更大，移动左指针
if ((long) middle * middle < num) {
left = middle + 1;
}
// 如果 middle 的平方大于 num，说明平方根可能更小，移动右指针
else if ((long) middle * middle > num) {
right = middle - 1;
}
// 如果 middle 的平方等于 num，说明找到了完全平方数，返回 true
else {
return true;
}
}
// 如果无法找到完全平方数，返回 false
return false;
}
}