算法训练-6高效算法部分 二分查找
6.2 二分查找
前言
二分查找的思想非常简单，在有序的数据中每次按照中点进行尝试，如果中间点大于我们要查找的值，则答案应该位于左侧， 反之右侧。由于每次可以排除现有数据量的一半，因此时间复杂度是。
以下我们提供两套二分查找的模板。两个模板的原理都是一样的，区别在于边界的处理。二分查找的难点往往也在于边界。因此如果我们划分的边界是[l,mid]和[mid + 1, r]那我们选择模板1。如果我们划分的边界是[0,mid-1]和[mid,r] 那我们选择模板2。
int bsec1(int l, int r)
{
while (l < r)
{
int mid = (l + r)/2;
if (check(mid)) r = mid;
else l = mid + 1;
}
return r;
}
int bsec2(int l, int r)
{
while (l < r)
{
int mid = ( l + r + 1 ) /2;
if (check(mid)) l = mid;
else r = mid - 1;
}
return r;
}- 找到恰好等于目标值
int lf = 0, rt = nums.length - 1;
while (lf < rt) {
int mid = (lf + rt) >> 1;
if (nums[mid] >= target) rt = mid;
else lf = mid + 1;
}
return nums[rt] == target ? rt : -1;- 找到第一个大于等于目标值
int lf = 0, rt = nums.length - 1;
while (lf <= rt) {
int mid = (lf + rt) >> 1;
if (cur == target) return mid;
else if (cur > target) rt = mid - 1;
else lf = mid + 1;
}
return lf;- 找到第一个大于目标值
int lf = 0, rt = n - 1;
while (lf < rt) {
int mid = ((lf - rt) >> 1) + rt;
if (cur > target) rt = mid;
else lf = mid + 1;
}
return rt;- 找到小于等于目标值的最大值【最小值最大】
int lf = 0, rt = x;
while (lf < rt) {
int mid = (lf + rt) >> 1;
if (check(mid)) rt = mid;
else lf = mid + 1;
}
return rt;二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。题目解析
由于数组是有序的，因此可以使用二分进行查找。
假设说 nums[mid] >= target ，则说明此时应该在 [lf, mid] 中寻找答案，那么r = mid；因此我们套用模板二即可。
当然如果不存在应该返回-1。
代码解析
class Solution {
// search 方法用于在升序数组 nums 中查找目标值 target
// 如果找到目标值，则返回其索引；如果未找到，则返回 -1
public int search(int[] nums, int target) {
// 初始化左右指针 lf 和 rt，分别指向数组的起始位置和结束位置
int lf = 0, rt = nums.length - 1;
// 使用 while 循环进行二分查找，当左指针小于右指针时继续查找
while (lf < rt) {
// 计算中间位置的索引，使用无符号右移操作符 ">>" 避免溢出
int mid = (lf + rt) >> 1;
// 如果中间位置的元素大于等于目标值，则在左半部分继续查找
if (nums[mid] >= target) {
rt = mid;
} else {
// 否则，在右半部分继续查找
lf = mid + 1;
}
}
// 在退出循环时，如果右指针所指向的元素等于目标值，则返回其索引 rt
// 如果不等于目标值，说明未找到目标值，返回 -1
return nums[rt] == target ? rt : -1;
}
}x 的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 2^31 - 1题目解析
由于不能使用库函数，因此我们需要“对答案进行二分”。
答案可能的范围是 [0, x]，因此我们要二分的思路枚举这个区间。
但是要舍去小数的部分，换个说法就是找到区间 [0, x] 中小于等于x的最大值。
最小值最大的问题也是二分的一个经典标志。
如果 mid^2 大于等于 x，则说明此时应该在 [l, mid] 之间找答案，反之则是 [mid + 1, r] 。因此套用模板2即可。
代码展示
class Solution {
// mySqrt 方法用于计算并返回整数 x 的平方根
// 使用二分查找算法在 [0, x] 的范围内查找最接近 x 的平方数的整数次方
public int mySqrt(int x) {
// 初始化左右指针 lf 和 rt，分别指向搜索范围的起始点和结束点
int lf = 0, rt = x;
// 使用 while 循环进行二分查找，当左指针小于右指针时继续查找
while (lf < rt) {
// 计算中间位置的索引，使用无符号右移操作符 ">>" 避免溢出
int mid = (lf + rt) >> 1;
// 计算中间值的平方，使用 long 类型避免在计算大数时溢出
long cur = (long) mid * mid;
// 如果中间值的平方大于等于目标数 x，则在左半部分继续查找
if (cur >= x) {
rt = mid; // 更新右指针
} else {
// 如果小于目标数，则在右半部分继续查找
lf = mid + 1; // 更新左指针
}
}
// 在退出循环时，检查右指针所指向的数的平方是否正好等于目标数 x
// 如果是，则返回右指针的值，即 x 的平方根
// 如果不是，返回右指针的值减 1，因为在二分查找中，已经确保了该值的平方小于 x 且是小于等于 x 的所有平方数中最大的
return (long)rt * rt == x ? rt : rt - 1;
}
}搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 的算法。
示例 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 <= 10^4
-10^4 <= nums[i] <= 10^4
nums 为 无重复元素 的 升序 排列数组
-10^4 <= target <= 10^4题目描述
等价于找到大于等于 target 的最小值的下标
代码展示
class Solution {
// searchInsert 方法用于在一个升序数组 nums 中找到目标值 target 的插入位置
// 即使目标值在数组中不存在，该方法也能找到其合适的插入位置，以保持数组的有序性
public int searchInsert(int[] nums, int target) {
// 初始化左指针 lf 和右指针 rt，分别指向数组的开始和结束
int lf = 0, rt = nums.length;
// 使用 while 循环进行二分查找，当左指针小于右指针时继续查找
while (lf < rt) {
// 计算中间位置的索引，使用无符号右移操作符 ">>" 避免溢出
int mid = (lf + rt) >> 1;
// 如果中间位置的元素大于等于目标值，则在左半部分继续查找
if (nums[mid] >= target) {
rt = mid; // 更新右指针为 mid，因为 target 应该在 [lf, mid] 范围内
} else {
// 如果中间位置的元素小于目标值，则在右半部分继续查找
lf = mid + 1; // 更新左指针为 mid + 1，因为 target 应该在 [mid + 1, rt) 范围内
}
}
// 在退出循环时，左指针和右指针相遇，即 lf == rt
// 此时，rt 指向的位置就是目标值 target 应该插入的位置
// 如果目标值在数组中已存在，则 rt 指向的就是目标值的位置
// 如果目标值不在数组中，则 rt 指向的就是目标值应该插入的第一个大于或等于 target 的位置
return rt;
}
}第一个错误的版本
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例 1：
输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
示例 2：
输入：n = 1, bad = 1
输出：1
提示：
1 <= bad <= n <= 2^31 - 1题目解析
代码展示
public class Solution extends VersionControl {
// firstBadVersion 方法用于找出第一个错误版本的编号
// 假设有一个版本控制系统，版本编号从 1 到 n，其中第 i 个版本是 badVersion 函数的一个调用
// 该方法使用二分查找算法来确定第一个错误版本的编号
public int firstBadVersion(int n) {
// 初始化左右指针 l 和 r，分别指向可能的第一个错误版本的最小和最大编号
int l = 1, r = n;
// 使用 while 循环进行二分查找，当左指针小于右指针时继续查找
while (l < r) {
// 计算中间位置的索引，使用无符号右移操作符 ">>" 避免溢出
// 由于 l 和 r 相减可能会溢出，所以先进行减法操作，再右移一位
int mid = ((l - r) >> 1) + r;
// 调用 isBadVersion 方法检查 mid 是否是错误版本
// 如果是错误版本，则第一个错误版本必定在 [l, mid] 范围内，因此将 r 更新为 mid
if (isBadVersion(mid)) {
r = mid;
}
// 如果 mid 不是错误版本，则第一个错误版本必定在 [mid + 1, r] 范围内，因此将 l 更新为 mid + 1
else {
l = mid + 1;
}
}
// 在退出循环时，左指针和右指针相遇，即 l == r
// 此时，l（或 r）指向的就是第一个错误版本的编号
return r;
}
}寻找峰值
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(logn) 的算法来解决此问题。
示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；或者返回索引 5， 其峰值元素为 6。
提示：
1 <= nums.length <= 1000
- 2^31 <= nums[i] <= 2^31 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]题目解析
代码展示
class Solution {
// findPeakElement 方法用于找出一个数组中的峰值元素
// 数组中峰值的定义是：元素的值大于它的左右相邻元素
public int findPeakElement(int[] nums) {
// 初始化左右指针 l 和 r，分别指向数组的起始位置和结束位置
int l = 0, r = nums.length - 1;
// 使用 while 循环进行二分查找，当左指针小于右指针时继续查找
while (l < r) {
// 计算中间位置的索引 mid，使用无符号右移操作符 ">>" 避免在计算中发生溢出
int mid = ((l - r) >> 1) + r;
// 比较中间元素与其右侧相邻元素的值
// 如果 mid 位置的元素小于其右侧相邻元素，则峰值一定在 mid + 1 的右侧，更新左指针为 mid + 1
if (nums[mid] < nums[mid + 1]) {
l = mid + 1;
} else {
// 否则，峰值一定在 mid 或者 mid 的左侧，更新右指针为 mid
r = mid;
}
}
// 当左指针 l 与右指针 r 相遇时，循环结束
// 此时 l（或 r）即为数组中的峰值元素的索引，直接返回
return r;
}
}爱吃香蕉的珂珂
珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。
珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。
示例 1：
输入：piles = [3,6,7,11], h = 8
输出：4
示例 2：
输入：piles = [30,11,23,4,20], h = 5
输出：30
示例 3：
输入：piles = [30,11,23,4,20], h = 6
输出：23
提示：
1 <= piles.length <= 10^4
piles.length <= h <= 10^9
1 <= piles[i] <= 10^9题目解析
代码展示
class Solution {
// minEatingSpeed 方法用于计算在 h 小时内吃完所有香蕉的最小速度
// piles 数组表示各个香蕉堆的数量，h 表示分配香蕉的小时数
public int minEatingSpeed(int[] piles, int h) {
// 计算所有香蕉的总数
long sum = 0;
for (int pile : piles) {
sum += pile;
}
// 初始化左右指针 l 和 r，分别表示吃香蕉速度的最小值和最大值
long l = 1, r = sum;
// 使用二分查找算法来确定最小吃香蕉的速度
while (l < r) {
// 计算中间速度
long mid = ((l - r) >> 1) + r;
// 使用 check 方法检查当前速度 mid 是否能在 h 小时内吃完所有糖果
if (check(mid, piles, h)) {
r = mid; // 如果可以，那么最小速度可能在 [l, mid] 范围内，更新右指针
} else {
l = mid + 1; // 如果不可以，最小速度可能在 [mid + 1, r] 范围内，更新左指针
}
}
// 当 l 和 r 相遇时，循环结束，此时 r 即为所求的最小吃香蕉速度，返回 r 的整数值
return (int)r;
}
// check 方法用于检查给定的吃香蕉速度 x 是否能在 h 小时内吃完所有香蕉
boolean check(long x, int[] piles, int h) {
int cnt = 0; // 初始化所需小时数
// 遍历所有香蕉堆，计算以速度 x 吃完它们所需的小时数
for (int pile : piles) {
// 如果香蕉堆的数量能被速度 x 整除，则所需小时数为香蕉数量除以速度
if (pile % x == 0) {
cnt += pile / x;
} else {
// 如果不能整除，需要额外加一小时来吃完剩余的香蕉
cnt += (pile / x) + 1;
}
}
// 如果所需小时数小于等于 h，则返回 true，表示速度 x 可行
return cnt <= h;
}
}有效的完全平方数
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true，否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
进阶：不要 使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16
输出：true
示例 2：
输入：num = 14
输出：false
提示：
1 <= num <= 2^31 - 1题目解析
由于不能使用库函数，因此我们需要对答案进行二分。
初始的二分区间可以定义为[0, num]。
代码展示
class Solution {
// isPerfectSquare 方法用于判断给定的整数 num 是否为一个完全平方数
// 一个完全平方数是一个整数，它可以表示为另一个整数的平方
public boolean isPerfectSquare(int num) {
// 初始化左右指针 l 和 r，l 从 0 开始，r 从 num 开始
int l = 0, r = num;
// 使用 while 循环进行二分查找，当左指针小于右指针时继续查找
while (l < r) {
// 计算中间位置的索引 mid，使用无符号右移操作符 ">>" 避免溢出
int mid = ((l - r) >> 1) + r;
// 检查 mid 的平方是否大于等于 num
// 如果是，说明可能的完全平方根在 [l, mid] 范围内，更新右指针为 mid
if ((long)mid * mid >= num) {
r = mid;
} else {
// 如果不是，说明可能的完全平方根在 [mid + 1, r] 范围内，更新左指针为 mid + 1
l = mid + 1;
}
}
// 在退出循环时，左指针和右指针相遇，即 l == r
// 此时，r 指向的值是 num 的可能的完全平方根
// 检查 r 的平方是否等于 num，若是，则 num 是完全平方数，返回 true
// 否则，num 不是完全平方数，返回 false
return r * r == num;
}
}寻找比目标字母大的最小字母
给你一个排序（非递减顺序）后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。如果不存在这样的字符，则返回 letters 的第一个字符。
在比较时，字母是依序循环出现的。举个例子：
如果目标字母 target = ‘z’ 并且字符列表为 letters = [‘a’, ‘b’]，则答案返回 ‘a’
示例 1：
输入: letters = [“c”, “f”, “j”]，target = “a”
输出: “c”
示例 2:
输入: letters = [“c”,“f”,“j”], target = “c”
输出: “f”
示例 3:
输入: letters = [“c”,“f”,“j”], target = “d”
输出: “f”
提示：
2 <= letters.length <= 10^4
letters[i] 是一个小写字母
letters 按非递减顺序排序
letters 最少包含两个不同的字母
target 是一个小写字母题目解析
此题转换为：找到数组中第一个大于target的字符。
代码展示
class Solution {
// nextGreatestLetter 方法用于在字符数组 letters 中找出第一个大于目标字符 target 的字符
// 如果所有字符都小于等于 target，则返回数组的第一个字符
public char nextGreatestLetter(char[] letters, char target) {
// 初始化左右指针 l 和 r，分别指向数组的起始位置和末尾位置（不包括末尾）
int l = 0, r = letters.length - 1;
// 使用 while 循环进行二分查找，当左指针小于右指针时继续查找
while (l < r) {
// 计算中间位置的索引 mid，使用无符号右移操作符 ">>" 避免溢出
int mid = (l + r) >> 1;
// 比较中间字符 letters[mid] 与目标字符 target
// 如果 letters[mid] 大于 target，则说明大于 target 的字符可能在 [l, mid] 范围内，更新右指针 r 为 mid
if (letters[mid] > target) {
r = mid;
} else {
// 如果 letters[mid] 小于或等于 target，则说明大于 target 的字符可能在 [mid+1, r] 范围内（包括 mid），更新左指针 l 为 mid + 1
l = mid + 1;
}
}
// 循环结束后，右指针 r 指向的位置可能是大于 target 的最小字符，但也可能是 target 本身或小于 target 的字符
// 因此需要检查 letters[r] 是否大于 target
// 如果大于，则返回 letters[r]，因为它是大于 target 的最小字符
if (letters[r] > target) {
return letters[r];
} else {
// 如果 letters[r] 不大于 target，说明所有字符都小于等于 target，或者大于 target 的字符不在 [l, r] 范围内
// 根据题意，这种情况下返回数组的第一个字符 letters[0]
return letters[0];
}
}
}在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 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 <= 10^5
- 10^9 <= nums[i] <= 10^9
nums 是一个非递减数组
- 10^9 <= target <= 10^9代码展示
class Solution {
// searchRange 方法用于找出给定数组 nums 中目标值 target 的第一个和最后一个索引
// 如果目标值不在数组中，则返回 {-1, -1}
public int[] searchRange(int[] nums, int target) {
// 如果数组为空，直接返回 {-1, -1}
if (nums.length == 0) return new int[]{-1, -1};
// 第一部分：找到第一个等于 target 的值
int l = 0, r = nums.length - 1;
while (l < r) {
// 计算中间索引 mid，使用无符号右移操作防止溢出
int mid = (l + r) >> 1;
// 根据 nums[mid] 与 target 的大小关系调整左右指针
if (nums[mid] >= target) r = mid; // target 在左半边
else l = mid + 1; // target 在右半边
}
// 如果 r 指针所指向的元素不等于 target，说明 target 不在数组中，返回 {-1, -1}
if (nums[r] != target) return new int[]{-1, -1};
// 保存第一个等于 target 的元素的索引
int first = r;
// 重置左右指针，寻找最后一个等于 target 的值
l = 0;
r = nums.length - 1;
while (l < r) {
// 计算中间索引 mid，这里使用 (l + r + 1) 确保 mid 偏向右半边
int mid = (l + r + 1) >> 1;
// 根据 nums[mid] 与 target 的大小关系调整左右指针
if (nums[mid] > target) r = mid - 1; // target 在左半边
else l = mid; // target 在右半边或等于 mid
}
// 返回第一个和最后一个等于 target 的元素的索引
return new int[]{first, r};
}
}分割数组的最大值
给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。
示例 1：
输入：nums = [7,2,5,10,8], m = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
示例 2：
输入：nums = [1,2,3,4,5], m = 2
输出：9
示例 3：
输入：nums = [1,4,4], m = 3
输出：4
提示：
1 <= nums.length <= 1000
0 <= nums[i] <= 10^6
1 <= m <= min(50, nums.length)代码展示
class Solution {
// splitArray 方法用于找出数组 nums 可以被分割为 m 部分的最小总和
// 其中每部分的总和不超过 x，返回满足条件的最小 x
public int splitArray(int[] nums, int m) {
// 计算数组 nums 的总和
int sum = 0;
for (int num : nums) {
sum += num;
}
// 初始化左右指针 l 和 r，分别表示最小总和和最大总和
int l = 0, r = sum;
// 使用二分查找算法在 [l, r] 范围内查找满足条件的最小 x
while (l < r) {
// 计算中间值 mid
int mid = (l + r) >> 1;
// 使用 check 方法检查当前的 mid 是否满足条件
if (check(mid, nums, m)) {
r = mid; // 如果满足条件，更新右指针为 mid，因为可能存在更小的值
} else {
l = mid + 1; // 如果不满足条件，更新左指针为 mid + 1，因为需要更大的值
}
}
// 返回找到的最小总和 x
return r;
}
// check 方法用于检查是否存在一个 x 值，使得数组 nums 可以被分割为 m 部分，每部分的总和不超过 x
boolean check(int x, int[] nums, int m) {
int cnt = 1; // 初始化分割的部分数量为 1
int cur = 0; // 初始化当前部分的总和为 0
// 遍历数组 nums
for (int i = 0; i < nums.length; i++) {
// 如果当前元素加上当前部分的总和不超过 x，则将其加入当前部分
if (cur + nums[i] <= x) {
cur += nums[i];
} else {
// 如果当前元素大于 x，则无法分割，返回 false
if (nums[i] > x) {
return false;
}
// 否则，开始新的部分，更新当前部分的总和为当前元素的值，并增加分割的部分数量
cur = nums[i];
cnt++;
}
}
// 返回分割的部分数量是否不超过 m
return cnt <= m;
}
}算法训练-6高效算法部分 二分查找
https://blog.fulequn.online/2024/05/Article202405051/