二分方法
二选一查找(轮转数组,sqrt,找第k大数等)
动态规划有状态和递推公式; 而二分法有解区间[l, r]和区间的二分方式。
注意解区间的边界, 尤其不要把解区间跟题目原有的区间混淆,二者的边缘往往不一样。比如原题有【0, n-1】,则解区间可能是【1,n-2】;此外mid是否能被判别为答案,也是变化的因素。
还要注意区间中点计算:(l+r)/2不会超过[l, r]的一半。 奇数下 [1, mid=2, 3],偶数下 [1, 2, mid=2.5=2, 3, 4].
中点(l+r)/2 被广泛应用在区间翻转中for(i=L;i<=mid=(l+r)/2;i++)...和 区间划分中:[l,r] =......
阅读全文