🌸二分查找法模板
掌握二分查找的两种思路：
思路 1：在循环体内部查找元素：while (left <= right)；思路 2：在循环体内部排除元素：while (left < right)。 全部使用左闭右闭区间，不建议使用左闭右开区间，反而使得问题变得复杂；
在循环体内部查找元素（解决简单问题时有用）
class Solution {
public int search(int[] nums
, int target
) {
int len
= nums
.length
;
if (len
== 0) {
return -1;
}
int left
= 0;
int right
= len
- 1;
while (left
<= right
) {
int mid
= left
+ (right
- left
) / 2;
if (nums
[mid
] == target
) {
return mid
;
} else if (nums
[mid
] > target
) {
right
= mid
- 1;
} else {
left
= mid
+ 1;
}
}
return -1;
}
}
int mid = (left + right) / 2;在left + right整形溢出的时候，mid会变成负数，回避这个问题的办法是写成int mid = left + (right - left) / 2;
在循环体内部排除元素（在解决复杂问题时非常有用）
public int search(int[] nums
, int left
, int right
, int target
) {
while (left
< right
) {
int mid
= left
+ (right
- left
) / 2;
if (check(mid
)) {
left
= mid
+ 1
} else {
right
= mid
}
}
}
public int search(int[] nums
, int left
, int right
, int target
) {
while (left
< right
) {
int mid
= left
+ (right
- left
+ 1) / 2;
if (check(mid
)) {
right
= mid
- 1;
} else {
left
= mid
;
}
}
}
核心思想：把待搜索的目标元素放在最后判断，每一次循环排除掉不存在目标元素的区间，目的依然是确定下一轮搜索的区间；特征：while (left < right)，这里使用严格小于 < 表示的临界条件是：当区间里的元素只有 2 个时，依然可以执行循环体。换句话说，退出循环的时候一定有 left == right 成立，这一点在定位元素下标的时候极其有用；在循环体中，先考虑nums[mid]在满足什么条件下不是目标元素，进而考虑两个区间[left, mid - 1]以及[mid + 1, right]里元素的性质，目的依然是确定下一轮搜索的区间；
注意 1：先考虑什么时候不是解，是一个经验，在绝大多数情况下不易出错，重点还是确定下一轮搜索的区间，由于这一步不容易出错，它的反面（也就是 else语句的部分），就不用去考虑对应的区间是什么，直接从上一个分支的反面区间得到，进而确定边界如何设置； 根据边界情况，看取中间数的时候是否需要上取整；
注意 2： 这一步也依然是根据经验，建议先不要记住结论，在使用这个思想解决问题的过程中，去思考可能产生死循环的原因，进而理解什么时候需要在括号里加 1 ，什么时候不需要； 在退出循环以后，根据情况看是否需要对下标为 left 或者 right 的元素进行单独判断，这一步叫「后处理」。在有些问题中，排除掉所有不符合要求的元素以后，剩下的那 1 个元素就一定是目标元素。如果根据问题的场景，目标元素一定在搜索区间里，那么退出循环以后，可以直接返回 left（或者 right）。
🌸滑动窗口算法的代码框架
大致逻辑
int left = 0, right = 0;
while (right < s.size()) {`
// 增大窗口
window.add(s[right]);
right++;
while (window needs shrink) {
// 缩小窗口
window.remove(s[left]);
left++;
}
}
框架模板
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
