二分方法
- 二选一查找（轮转数组，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] => [l, mid], [mid+1, r]
- # * # 被 (l+r)/2 划分成【## 】【#】或者【#】【#】，在总区间长度为奇数时，左子区间会比右边多一个元素；
- 如果取mid=(l+r-1)/2，也可以用于区间划分。# * # 被 (l+r-1)/2 划分成【# 】【##】或者【#】【#】。显然，它与上面的区别在于： 在偶数长情况下得到结果和(l+r)/2相同；奇数长情况下它得到偏左的元素，相应地它的左子区间会比右边少一个元素；而(l+r)/2刚好得到正中间的值，所以左子区间比右边多一个元素。 它也可以用于区间翻转 for(;
i<= mid=(l+r-1)/2; i++).
- 二路DFS 如线段树， 快排 归并 。
1. 快排
写法一
void sort(int a[], int n){
if(n<=1) return;
int m = a[0], l = 1, r = n-1;
while(l<r){
while(l<r && a[l]<=m) l++;
while(l<r && a[r]>m) r--;
if(l<r) {
int tmp = a[l];
a[l] = a[r], a[r] = tmp;
}
}
/* [1, l) no bigger than m,(r, n-1] bigger than m, l==r */
assert(l == r);
if(a[r] > m) r--;
/* now a[r] <= m, r>=0 */
a[0] = a[r], a[r] = m;
sort(a, r);
sort(a+r+1, n-r-1);
}
写法二
void sort(int a[], int n){
if(n<=1) return;
int m = a[0], l = 0, r = n-1;
// no less than 2 elements in a[], l=0<r
while(l<r){
while(l<n && a[l]<=m) l++;// l skip 0, and may stop in bigger than r=n-1
while(r>=0 && a[r]>m) r--;// r stop in no smaller than l=0, since a[0]<=m
if(l<r) {// then l and r can't overindex
int tmp = a[l];
a[l] = a[r], a[r] = tmp;
}
}
/* a[r] no bigger than m, (r, n-1] bigger than m */
a[0] = a[r], a[r] = m;
sort(a, r);
sort(a+r+1, n-r-1);
}
sort colors
class Solution {
public:
void sortColors(int A[], int n) {
int l = 0, r;
for(int m=0; m<2; m++){
r=n-1;
while(l<r){//l是划分点:A[l]是第一个大于m的元素，并且l就算越界，也会有r约束它使之跳过while循环
while(l<r && A[l]<=m) l++;
while(l<r && A[r]>m) r--;
if(l<r) { int t = A[l]; A[l]=A[r], A[r]=t;}
}
}
}
};
但是奇怪的是上面的代码没有这个快？ O（n*1）>O（n*3)....
void sortColors(int A[], int n) {
for(int m=0; m<2; m++){
int l = 0, r = n-1;
while(l<r){
while(l<r && A[l]<=m) l++;
while(l<r && A[r]>m) r--;
if(l<r) { int t = A[l]; A[l]=A[r], A[r]=t;}
}
}
}
2. 轮转数组
找最小数
如 轮转数组3 4 5 1 2, 返回 1
二分方法：
l =0, r = n-1, t = a[r]
跳过a[l]==t的l
assert(a[l]!=t) //l在左半边 或 右半边
while ...
if a[mid]>t: l = mid+1 //mid落在左半边
if a[mid]<=t: r = mid //mid落在右半边,注意右半边的mid有可能是答案，r=mid而不是mid-1
注意存在这种情况 x x x x1 x2 .. xm, y1 y2 .. yn x x x x ，即两边都存在 重复x， 如 3 3 4 5 1 2 3 3 3,
这种情况的处理办法是 先跳过左边的 a[l]==t 的l
class Solution {
public:
int findMin(vector<int> &num) {
int l = 0, r = num.size() - 1;
int t = num[r];
//while(l<r) if(num[l] == t) l++; //@error
while(l<r && num[l] == t) l++;
while(l<r){
int mid = (l+r)/2;
if(num[mid]>t) l = mid+1;
else r = mid; // if num[mid] == t, then a[mid, r] == t, let r = mid
}
return num[l];
}
};
找第k小数
（待续）
3. 双有序数组
找第k小数/中位数
要想清楚每个细节，还是挺费事的，
http://blog.csdn.net/brandohero/article/details/38342749
class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
int t = m+n;
if(t%2){
return findK(A, m, B, n, (m+n-1)/2+1);
}
return (findK(A, m, B, n, (m+n-1)/2+1) + findK(A, m, B, n, (m+n-1)/2+2))/2.0;
}
int findK(int A[], int m, int B[], int n, int k){
assert(k>=1 && k<= m+n);
int l = m-1, r = n-1;
while(l>=0 && r>=0 && l+r+2>=k+1){
int m1 = (k+1)*(l+1)/(l+r+2)-1, m2 = k-1-m1;
if(m1<0) m1=0, m2 = k-1;//@error: not if(m2>r) m2=r, m1=k-1-m2;
if(A[m1]>B[m2]) l = m1 - 1;
else r = m2 -1;
}
if(l>=0 && r>=0) return max(A[l], B[r]);
//return l<0?B[r]:A[l];//@error: should be B[k-1] or A[k-1].
return l<0?B[k-1]:A[k-1];
}
};
4 sqrt
一般的二分查找都是 <l, r> => <l, mid-1>,mid, <mid+1, r>
class Solution {
public:
int sqrt(int x) {
int l =0, r= x;
while(l<r){
int mid = (l+r)/2;
long long int t = mid*(long long int)mid;
if(t > x) {
r = mid-1;
}
else{//t<=x
if( t == x || (mid+1)*(long long int)(mid+1) > x) return mid; // if mid+1 is too big
l = mid+1;
}
}
return l;
}
};
5 数组波峰
题目来自九章算法
解答
- 一开始解区间为[l, r] = [1， n-2]且l<=r，
- 探测mid是否是解(a[mid]>a[mid-1] && a[mid]>a[mid+1])，如果是返回
- a[mid ] < a[mid+1]: 则在右边[mid+1, r]
- a[mid ] > a[mid+1]: 在左边 [l, mid-1]
int find(int a[], int n){
int l = 1, r = n-2;
while(l<=r){
int mid =(l+r)/2;
if(a[mid]>a[mid+1] && a[mid] > a[mid-1]) return mid;
if(a[mid]>a[mid+1]) {r=mid-1;}
else l = mid+1;
}
return -1; // not found
}