首页 > 代码库 > 分治法--二分查找、乘方、斐波那契数
分治法--二分查找、乘方、斐波那契数
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 ) left = mid+1; 13 else 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=left int 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 showed int 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]<k ) left = mid+1; else{ right = mid-1; last = mid; } } return last; } //find the first location that a[location]>k int 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。