今天的专题是二分法——二分答案，英文叫Binary Search on Result。
这种题的特点是往往没有给你一个数组让你二分同样是找到满足某个条件的最大或者最小值。
先总结两道相似的题，两道题来自Lintcode，因为Leetcode上没有这两道题
完整的c++代码如下：
class Solution
{
public:
int woodCut(vector<int> &L, int k)
{
// write your code here
int l = 1;
int r = 0;
for (int item : L)
{
r = std::max(r, item);
}
while (l + 1 < r)
{
int mid = l + (r - l) / 2;
if (count(L, mid) >= k)
{
l = mid;
}
else
{
r = mid;
}
}
if (count(L, r) >= k)
{
return r;
}
if (count(L, l) >= k)
{
return l;
}
return 0;
}
private:
int count(vector<int> &L, int len)
{
int sum = 0;
for (int item : L)
{
sum = sum + item / len;
}
return sum;
}
};
当跳出while循环后，L = L, mid = L + 1, R = R + 2。
L表示Mid左边的最大值，R表示mid右边的最小值。
跳出while循环后，重新再验证一下就好。
算是一个模板题，再看看下一道。
不过这个题比较复杂啦。它的难点在于check()函数的逻辑。(当然这个题我还没有完全把逻辑盘对！)
就是判断当前的左右边界L和R所确定的二分边界mid是否何理，不合理的话，则更新边界R或者L。
check中有一个num变量，表示复印完 n 本书需要的人数。
核心是2点：
- 将尽可能多的书分给同一个人
- 判断复印完 n 本书需要的人数num是否不大于 k.
这个题刚开始比较懵，是被check()函数中的left变量迷惑了。一直把left当下界看，当成一个向量在看，从mid出发，指向左无穷大的向量。导致一直没理解，其实Left变量就是表示一个标量，想象成一条线段，表示还可以使用的时间额度。刚开始没有，left=0，说明没有可用的时间额度，那么来一个人，多一个人就增加了时间额度。
如果当前item在当前的时间额度中，就是item<=left，那么这个item复印完后，left清为0，或者left - item。很好理解。其他的就是模板。
因为书籍复印一开始没太懂，所以在VS中调试了，下面给出VS2019调试的代码——
#include "C.h"
vector<int> pages = { 3, 2, 4 };
int k = 3;
bool check(vector<int>& pages, int limit, int k)
{
int num = 0;
int left = 0;
for (int item : pages)
{
// 如果当前书的页数比mid大，说明mid边界取错了
// 我们让left=0表示假定ans的范围是在left~mid之间
// 但如果我们复印第i本书花的时间比limit大，那说明当前确定的范围是错的
if (item > limit)
{
return false;
}
// 当item比left大的时候，说明ans是在left~limit之间的
// 那么说明第i本书可复印，num++
// 当前第1次这个item是3，比left左边界为0要大
// 但我们知道当前item=3是<=limit的
if (item > left)
{
num++;
left = limit;
}
left = left - item;
}
// num是什么，为什么要拿num和k比较呢？
// num是复印完 n 本书需要的人数
return num <= k;
}
// Binary Search
int copyBooks(vector<int>& pages, int k)
{
// write your code here
int l = 2;
int r = 9;
// template
// while()函数的目的就是在不断地确定左右边界l和r
while (l + 1 < r)
{
int mid = l + (r - l) / 2;
// check()函数的作用就是判断ans到底是在mid左边还是mid右边
if (check(pages, mid, k))
{
r = mid;
}
else
{
l = mid;
}
}
if (check(pages, l, k))
{
return l;
}
return r;
}
int print()
{
int ans = copyBooks(pages, k);
printf("%d", ans);
return 0;
}
int main()
{
copyBooks(pages, k);
print();
}
下面的题则是Leetcode中的题：
162. Find Peak Element
这道题使用了迭代二分查找算法。
思路：
- 首先我们要明白，一个数组中，可以有2个或者多个峰值元素。
- 假如当前中间这个元素mid比右边的第一个元素大，那就说明当前元素满足了当峰值元素的一半条件，我们找到了一个所谓的“备胎”，这样子就不用再往右看了！
这时候，将当前元素当成屏障。也就是把右边界移至当前元素的位置（r = mid）。这样可以将新的mid往屏障前面推，得到新的元素。- 得到的新的元素mid如果比右边的元素小，那么说明当前这个元素不能当做峰值元素，那么就继续往右找，因为L < R，所以一定可以找到一个元素，要不然就是上面2中定的呢个元素，要不然就是L在右移的过程中，碰到了比上面2中更大的元素，这样更大的就是答案。
- 第一次就可以判断出，答案是在左边范围还是右边范围！然后不断缩小范围！
// 迭代二分查找
class Solution
{
public:
int findPeakElement(vector<int>& nums)
{
int l = 0;
int r = nums.size() - 1;
while (l < r)
{
int mid = (l + r) / 2;
if (nums[mid] > nums[mid + 1])
{
r = mid;
}
else
{
l = mid + 1;
}
}
return l;
}
};
Lintcode75. 寻找峰值
再用下九章的解法，不过九章对应的是
两个题不太一样，我就分开总结吧。今天有点累，也没精力总结两道题了。后面一定要总结！！
Lintcode上通过了，但是时间复杂度好高！
完整代码：
class Solution
{
public:
int findPeak(vector<int>& A)
{
// if (A.size() <= 1) return 0;
int start = 1;
int end = A.size() - 2;
while(start + 1 < end)
{
int mid = start + (end - start) / 2;
// mid的求法和二分答案的不一样
if (A[mid] > A[mid + 1])
{
end = mid;
}
else
{
start = mid;
}
}
if (A[start] < A[end])
{
return end;
}
else
{
return start;
}
}
};
- 首先，数据上，LintCode 保证数据，第一个数比第二个数小，倒数第一个数比到倒数第二个数小。
- 每次mid求出的中间元素，如果start和end之间有4个元素，偶数个，则中间元素是较小的呢个，因为(end-start)/2是向下取整。
二分法。
每次取中间元素，如果中间元素大于左右，则这就是peek。
否则取大的一边。
如果左右两个都比自身大，可以随便取一边。
最终会找到peek。
正确性证明：
A[0] < A[1] && A[n-2] > A[n-1] 所以一定存在一个peek元素。
二分时，选择大的一边, 则留下的部分仍然满足1 的条件，即最两边的元素都小于相邻的元素。所以仍然必然存在peek。
二分至区间足够小，长度为3, 则中间元素就是peek。
核心就是：如果mid元素比右边大了，那么这个mid元素就作为新的右边界。只需要找左边比它小的元素了。
如果mid元素比右边小了，则这个mid元素作为新的左边界。
while条件是(start + 1 < end)，也就是剩start、mid、end最后三个元素的时候。
我们这么看，最后一次进while循环的情况，一定是这样——
start = start, end = start + 2,
然后
mid = start + 1
这样，如果中间元素比右边大，那么中间元素作为峰值元素候选人，end = mid。
这时就剩下2个元素，如果左大，那就是左边的元素，因为左边的元素再往左的呢些元素，已经被pass掉了，它们就是因为比右边的小，才被pass的。
如果中间元素比右边小，则end对应的元素是峰值元素，我们再比较一次start和end，如果start大，则start也比mid大，start是峰值。
如果是end，那么end是峰值，因为end右边的所有元素也是因为比它小，所以pass掉了。
69. Sqrt(x)
技巧：
- 直接对答案可能存在的区间进行二分 => 二分答案
- 判断区间的时候一个小技巧： mid * mid == x 中使用乘法可能会溢出，写成 mid == x / mid 即可防止溢出，不需要使用long或者BigInteger
- 剩下的是一样的，用下面这个代码的话，最后剩下的，就一定是两个元素，start和end。
- 如果end的平方比x大，则说明end不符合，返回start。如果end的平方比x小，那么则返回end。因为end是最接近sqrt(x)的值。
不过这道题虽然会了，但是对于start和end平方后的大小和x之间的比较还是不太明白。
譬如如果end平方比x大，返回了start，你怎么证明start的平方不会比x大？
33. Search in Rotated Sorted Array
这道题可能会总结得有些水，确实有些困了。
完整代码：
class Solution
{
public:
int search(vector<int>& nums, int target)
{
if (nums.empty() || nums.size() == 0)
{
return -1;
}
int start = 0;
int end = nums.size() - 1;
while(start + 1 < end)
{
int mid = start + (end - start) / 2;
if (nums[mid] == target)
{
return mid;
}
if (nums[start] < nums[mid])
{
if (nums[start] <= target && target <= nums[mid])
{
end = mid;
}
else
{
start = mid;
}
}
else
{
if (nums[mid] <= target && target <= nums[end])
{
start = mid;
}
else
{
end = mid;
}
}
}
if (nums[start] == target)
{
return start;
}
if (nums[end] == target)
{
return end;
}
return -1;
}
};
首先，我不明白这个解法，为什么是通过start和mid的大小，来划分两个区间。
也许是因为，我们的测试数据，是将一个升序数组的子数组反转了一下。
所以整个数组变换后，就是分成了2段，2段都是各自升序的。
所以我们先看start元素和Mid谁大，如果start比mid小，就先看start~mid这个区间。如果target在这个区间，则将end移动到mid的位置，也就是向左缩小了查找范围。
如果target不在这个区间，则将start移动到mid的位置，则是向右缩小了查找范围。
同理，如果start对应的元素比mid的大，将将注意力转移到mid~end这个区间。
如果target在这个区间，则将start向右移动到mid，向右缩小范围。
不在，则将end向左移动到mid，向左缩小范围。
最后，目标还是会缩小在start和end这俩身上，谁对应上了，就返回谁的下标。都没对应上，返回-1。
278. First Bad Version
完整代码：
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
class Solution
{
public:
int firstBadVersion(int n)
{
int start = 1;
int end = n;
while(start + 1 < end)
{
int mid = start + (end - start) / 2;
if (isBadVersion(mid))
{
end = mid;
}
else
{
start = mid;
}
}
if (isBadVersion(start))
{
return start;
}
return end;
}
};
用循环不变式来确定怎么写二分。
初始状态：答案肯定在[1,n]之间， 保证边界l不大于r。
每次循环：
- isBadVersion(mid) == false 答案肯定在[mid+1,r] 之间。
- isBadVersion(mid) == true 答案肯定在[l, mid] 之间。
确定输入条件防止死循环：
- 条件1中: l = mid+1， 那mid的值是l-1的话求解区域维持不变,就会死循环，然而除非r < l 不然mid不可能比l小， 所以不可能发生。
- 条件2中: r = mid, 那mid的值为r的话求解区域维持不变，会发生死循环。往回推 l = r 时有mid = l = r, 那么需要保证l != r 即 l < r 不会死循环。
所以while的条件至少要保证l < r, 如果想放松点 l+1 < r 也可以 。
终止条件：
- 给定 l < r的条件则l r 终止时指向相同元素(l == r)， 返回l或r都没有区别。
- 如果一定要用放松一点的条件 l+1 < r， 终止时边界指向相邻元素 比比返回需要的那个。
最后除了(l+1 < r)的代码外，再多一种——（l < r)这个版本的代码
。
class Solution {
public:
int findFirstBadVersion(int n) {
// write your code here
int l = 1, r = n;
while (l < r) {
int mid = l + (r-l) / 2;
if (isBadVersion(mid) == false) {
l = mid+1;
} else {
r = mid;
}
}
return l; // return r is valid as well
}
};
两个写法的区别有两处：
- while循环中，start = mid 和 l = mid + 1。
- 最后返回答案的时候——
if (isBadVersion(start))
{
return start;
}
return end;
和
return l;
因为第二种写法，l的更新一直是l = mid + 1。所以最后跳出while循环后，只剩下l对应的元素了。
第一种写法，跳出while循环后，最后剩start和end，所以再多判断一次。
