本文旨在记录看完灵神的二分查找算法视频后的心得
循环不变量
在二分查找中 开闭区间的选择, 左右下标的迭代, 循环条件的写法, 往往这些写法的多样化会使得在写二分查找的代码的时候反应很慢, 在总结二分查找的四种类型之前, 先初步了解一下循环不变量.
循环不变量是值算法在循环的过程中保持不变的一些性质.
尽管在循环过程中, 变量的值在变化不断, 循环条件在终止时也会发生变化, 但是仍有一些性质在循环的前中后都保持不变, 这样的性质的就是循环不变量.
这些循环不变量不一定是代码中的变量, 往往指代一些保持不变的现象和规律, 对二分查找或是其他算法, 不同的人在写代码时可能会倾向于不同的写法, 也会定义不同的循环不变量.
循环不变式主要用来帮助我们理解算法的正确性, 关于循环不变式, 我们必须证明三条性质.
初始化 循环的第一次迭代之前 不变式为真
保持 如果循环的某次迭代之前不变式为真 那么下次迭代之前它仍为真
终止 在循环终止时 不变式仍为真 该性质有助于证明算法是正确的
四种情形
以下面这个数组nums为例, 数组长度为n. 假设要找到数组中第一个大于等于8的元素的下标, 容易想到使用二分查找, 若左指针为L, 右指针为R, 此时我们可以按左右区间的类型划分出四种情形.
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 值 | 1 | 7 | 7 | 8 | 8 | 8 | 8 | 32 | 33 | 166 |
因为要找到第一个大于等于8的元素的下标, 那么分界点的值应该设置为8, 不能设置为9, 也不能设置为7. 因为每次迭代只能将数组分两半, 设置为9或者7的话, 最后终止时, 也只能得到以9或者7为分界的左右两半. 比如以9为分界, 第一个大于等于9的元素是32, 下标是7. 而以7为分界, 第一个大于等于7的元素是7. 下标为1. 但是我们想要的下标为3.
很容易联想到, 即使按照8分界, 这样得出的两半数组，我们也只知道一半的元素跟8的大小关系. 比如某次迭代中, 中间下标mid对应的元素为32, 那么我们只能知道mid以及mid右边的元素大于等于8, 而不知道mid左边的元素与8的大小关系. 而有时候又是只知道mid左边的元素与8的大小关系, 不知道mid右边的元素与8的大小关系, 因此单单靠mid这个变量的性质不足以构成循环不变量. 那么两个变量呢, 只要每次循环中, 我们将mid更新为左右下标L或者R, 这样通过L和R就可以将数组划分成三个部分. 左部分是0到L, 中间部分是L到R, 右部分是R到n. 很容易看出, 每次循环, 左部分都小于8, 而右部分都大于等于8, L到R的区间内则是未识别的元素. 而这就构成了三个循环不变量, 所以其实弄清楚L和R的具体含义, 就弄清楚了二分查找的循环不变量.
L区间左边的数都小于8
R区间右边的数都大于等于8
L到R区间内的数是未识别的数
左闭右闭
如果左右区间都是闭区间, 那么L被初始化为0, 而R被初始化为n - 1. 在mid被计算出来之时, nums[mid]的值也知道了, 并用来跟8作比较, 根据比较结果选择更新L或者是R. 换言之, 此时nums[mid]这个数跟8的大小关系也已经确定了, 因此nums[mid]这个元素是已被识别的元素, 而使用了闭区间, 就说明L和R所指向的元素都是包括在区间内的, 根据循环不变量3, L到R的区间都是未识别的数, 所以显然mid不能包括在L和R的区间内. 那么L和R在更新时, 代码如下.
1
2
3
4
5
6
7
8
while(L <= R) {
mid = (R - L) / 2 + L;
if(nums[mid] >= 8) {
R = mid - 1;
} else {
L = mid + 1;
}
}
所以循环结束时, R在L的左边位置, 也就是R = L - 1. 因为此时区间[L, R]内不再包括任何数, 也就是说所有元素都已经被识别完毕, 所以依然满足循环不变量3. 而R右边的数仍然全部大于等于8, L左边的数仍然全部小于8, 满足循环不变量1和2. 此时返回L或者R+1的值, 即为第一个大于等于8的元素的下标.
左开右闭
左开右闭区间与上述情形的不同在于左指针L的更新. 因为L指向的是取不到的元素, 因此L指向的元素不属于L到R的区间, 所以L指向的元素已经被识别, 因此被识别的nums[mid]可以是L指向的元素, 所以L更新未mid即可, 循环结束时, L和R指向同一个位置, 这个位置的元素是取不到的, 满足循环不变式3. 代码如下.
1
2
3
4
5
6
7
8
while(L < R) {
mid = (R - L) / 2 + L;
if(nums[mid] >= 8) {
R = mid - 1;
} else {
L = mid;
}
}
左闭右开
与上述情形类似
1
2
3
4
5
6
7
8
while(L < R) {
mid = (R - L) / 2 + L;
if(nums[mid] >= 8) {
R = mid;
} else {
L = mid + 1;
}
}
左开右开
注意左右都是开区间的时候, 只需要满足L + 1 = R, 此时区间内就不会包括任何元素了.
1
2
3
4
5
6
7
8
while(L < (R - 1)) {
mid = (R - L) / 2 + L;
if(nums[mid] >= 8) {
R = mid;
} else {
L = mid;
}
}
一种题型
在面对其他题型时, 比如, 求第一个大于8的元素, 求最后一个小于等于8的元素, 求最后一个小于8的元素的题型时, 都可以使用循环不变量的分析方法. 四种题型其实是可以互相转换的. 上述四种情形是对大于等于8的分析, 在面对大于8的题型, 也就是求数组中第一个大于8的元素的下标, 其实就是求第一个大于等于9的元素的下标, 因为我们假设都是数组都是整数. 那么面对最后一个小于等于8的题型, 那就是先求出第一个大于等于9的元素的元素的下标, 然后下标减1, 也就是说第一个大于等于9的元素的左边那个数, 就是最后一个小于等于8的元素. 面对最后一个小于8的题型, 就是先求出第一个大于等于8的元素的下标, 然后下标再减1.
所以无论哪种题型, 都可以转换成大于等于的题型, 只需要记住大于等于的题型, 就能解决这类问题.
