二分查找-模板一
# 模板一
模板一用于寻找一个特定的数据，比如在一个有序数组中寻找一个特定值，是二分法的标准形式。
# 模板代码
# 区分语法
- 初始条件：left = 0, right = length-1
- 循环判断条件：left <= right
- 终止：left > right
- 向左查找：right = mid-1
- 向右查找：left = mid+1
# 代码
function binarySearch(nums, target) {
if (!nums.length) return -1;
// 区间，[left, right]
let left = 0;
let right = nums.length - 1;
while (left <= right) {
let mid = (left + right) >>> 1;
if (nums[mid] == target) return mid;
if (nums[mid] < target) {
// 在 [mid + 1, right] 区间继续寻找，注意不同模板不用区间下这里的写法
left = mid + 1;
} else {
// 在 [left, mid -1] 区间继续寻找，注意不同模板不用区间下这里的写法
right = mid - 1;
}
}
// End Condition: left > right，这种情况下无需再处理
return -1;
}
# 例题
这里用三个例子，由浅入深，说明模板一的应用。
# LC 374. 猜数字大小 (opens new window)
Q：
猜数字游戏的规则如下：
每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。 你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：
-1：我选出的数字比你猜的数字小 pick < num 1：我选出的数字比你猜的数字大 pick > num 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num 返回我选出的数字。
A：二分查找模板一的典型应用，为最基础用法。
/**
* @param {number} n
* @return {number}
*/
var guessNumber = function (n) {
// 时间复杂度：O(lg(n))
// 空间复杂度：O(1)
// 区间：[1, n]
let left = 1;
let right = n;
while (left <= right) {
let mid = (left + right) >>> 1;
let value = guess(mid);
if (value == 0) return mid;
if (value == 1) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
};
# LC 69. x 的平方根 (opens new window)
Q：
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
A：本题需要注意的点是，由于最后会抛弃小数部分，因此需要记录乘积小于x时的mid值。例如 求8的平方数，由于2 * 2 = 4，left会移动到3, 3*3=9，会超出结果，此时需要记录之前的mid
/**
* @param {number} x
* @return {number}
* 时间复杂度：O(lg(x))
* 空间复杂度：O(1)
*/
var mySqrt = function (x) {
if (x == 0) return 0;
// 区间 [0, x]
let left = 0;
let right = x;
let ans = 0;
while (left <= right) {
let mid = (left + right) >>> 1;
// 一般这里用除法，避免乘积溢出，为了看起直观，这里用乘法
let square = mid * mid;
if (square == x) return mid;
if (square < x) {
// 需要 记录 square < x时的 mid值
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
};
# LC 33. 搜索旋转排序数组 (opens new window)
Q：
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例：
输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4
A：这道题是模板一和二分法二段性概念的综合应用，需要从二分法的二段性出发考虑，辅助以折线图📈去理解。
数组已有序，如果以第一个或最后一个元素旋转，则依然都是升序，核心考虑中间元素旋转场景，如上图所示。对上面折线一分为二的情况有两种，每一种都会分为两种情况：一段确定有序，一段不确定。这是典型的二段性，因此可以使用二分法。
核心就是抓住确定性，在图中，C和D区域为确定有序的区域，可从两个区域任意区域入手，抓住这两个中的一个确定性
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function (nums, target) {
// 选取 确定性 C区域
{
// 区间 [0, nums.length - 1]
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = (left + right) >>> 1;
if (nums[mid] == target) return mid;
// 取确定性 左边 A段
// 注意这里 的 <= 中 = 一定要有，单个数组也属于 有序区间
if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) {
//这一段为 确定性，对应图中 A 区域，如果target如在此区间，则一定需要 right = mid - 1;否则就要异动left
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (target > nums[mid] && target <= nums[right]) {
//这一段为 确定性，对应图中 B 区域，如果target在此区间，则一定需要 left = mid + 1;，否则就要异动 right
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
// 选取 确定性 D区域
{
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = (left + right) >>> 1;
if (nums[mid] == target) return mid;
// 取确定性 右边 B段
// // 注意这里 的 <= 中 = 一定要有，单个数组也属于 有序区间
if (nums[mid] <= nums[right]) {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
} else {
if (target < nums[mid] && target >= nums[left]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}
return -1;
}
};
# 小结
- 模板一多用于寻找确定的树，即在某个区间内寻找确定的一个树
- 二分法的题目，尽量画折线图辅助思考