1、二分查找
常见错误:
- 死循环:循环体外的初始化条件,与循环体内的迭代步骤, 都必须遵守一致的区间规则,也就是说,如果循环体初始化时,是以左闭右开区间为边界的,那么循环体内部的迭代也应该如此.如果两者不一致,会造成程序的错误.
- 溢出:middle = left + (right - left) / 2
- 终止条件:一般来说,如果左闭右闭,则left<=right; 如果一开一闭,则left<right; 关键看left能不能等于right,而且要考虑实际情况,有时不能这样简单终结,会出现死循环,如下面的binarySearch_better()。
running time analysis:T(n) = T(n/2) + Θ(1) ---> T(n) = Θ(lgn)
正确算法:
1 //normal binarySearch without optimization, closed interval, return value is mid(maybe mid=left=right) 2 int binarySearch(int a[], int n, int k){ 3 if(n<1) return -1; 4 5 int left,right,mid; 6 left = 0; //closed left 7 right = n-1; //closed right 8 9 while( left<=right ){10 mid = left+(right-left)/2;11 12 if( a[mid]k ) right = mid-1;14 else return mid;15 }16 return -1;17 }
减少比较次数为1次
//more efficient way, left closed right away interval, return value is mid=leftint binarySearch_better(int a[], int n, int k){ if( n<1 ) return -1; int left,right, mid; left = 0; //closed left right = n; //open right while( left+1!=right ){ mid = left+(right-left)/2; if( a[mid]>k ) right = mid; else left = mid; } if( a[left]!=k || left<0 ) return -1; return left;} //find the location that k first showedint binarySearch_firstShow(int a[],int n, int k){ if( n<1 ) return -1; int left,right,mid,last; left=0; //closed left right=n-1; //closed right last=-1; //record the first place k showed while( left<=right ){ mid = left+(right-left)/2; if( a[mid]>k ) right = mid-1; else if( a[mid]kint binarySearch_firstBig(int a[],int n, int k){ if( n<1 ) return -1; int left,right,mid,last; left=0; //closed left right=n-1; //closed right last=-1; //record the first place k showed while( left<=right ){ mid = left+(right-left)/2; if( a[mid]>k ){ right = mid-1; last = mid; } else left = mid+1; } return last;}
2、斐波那契数
running time analysis:
- 采用递归,f(n) = f(n-1)+f(n-2),没有减少问题规模,反而扩大了,因为f(n-1)和f(n-2)的计算有重复的部分。
- 从f1一个一个加过来计算,时间为Θ(n);
- 缩减为非线性时间,采用规律:{f(n+1),f(n),f(n),f(n-1)} <==> a{1,1,1,0}^n,利用分治法,T(n) = T(n/2) + Θ(1) = Θ(lgn);
//{f(n+1),f(n),f(n),f(n-1)} <==> a{1,1,1,0}^n, return value is f(n)long long fibonacci( long long a[2][2],int n){ if(n==1){ a[0][0] = a[0][1] = a[1][0] = 1; a[1][1] = 0; return a[0][1]; } long long b[2][2]; fibonacci(b,n/2); for( int i=0; i<2; i++ ) for( int j=0; j<2; j++ ){ a[i][j] = 0; for( int k=0; k<2; k++ ) a[i][j] += b[i][k]*b[k][j]; } if( n%2==0 ) return a[0][1]; //n is odd, then a = a*{1,1,1,0}; int t1,t2; t1 = a[0][0]; t2 = a[0][1]; a[0][0] = t1+t2; a[0][1] = a[1][0] = t1; a[1][1] = t2; return a[0][1];}
3、乘方
running time analysis: T(n) = T(n/2) + Θ(1) = Θ(lgn)
//compute x^n.long long power(int x, int n){ if( n==1 ) return (long long)x; long long half = power(x,n/2); if( n/2*2 == n ) return half*half; return half*half*x;}
posted on 2014-05-14 22:03 阅读( ...) 评论( ...)