数据结构----算法--分治,快速幂

数据结构----算法–分治,快速幂

一.分治

1.分治的概念

分治法：分而治之

将一个问题拆解成若干个解决方式完全相同的问题

满足分治的四个条件

1.问题难度随着数据规模缩小而降低

2.问题可拆分

3.子问题间相互独立

4.子问题的解可合并

2.二分查找(折半搜索) BinaryChop

前提：有序

时间复杂度O(log2的n次方)

1.循环实现二分查找

//循环
int BinaryChop1(int a[], int begin, int end ,int find) {if (a == nullptr || begin > end) return -1;while (begin<= end) {int mid = begin+(end- begin)/2 ;if (a[mid] == find) {cout << "找到了,返回在数组中的下标" << endl;return mid;}else if (a[mid] < find) {begin = mid + 1;}else if (a[mid] > find) {end = mid - 1;}}return -1;
}

2.递归实现二分查找

//递归
int BinaryChop2(int a[], int begin, int end, int find) {if (a == nullptr || begin > end) return -1;int mid = begin+(end- begin)/2;if (a[mid] == find) {cout << "找到了，返回数组下标" << endl;return mid;}else if (a[mid] < find) {begin = mid + 1;}else if (a[mid] > find) {end = mid - 1;}return BinaryChop2(a, begin, end, find);}

二.快速幂

求一个数的幂次方

例如2的50次方

//简单写法，这种写法求一个数的幂次方速度慢
int a=2;
for(int i=0;i<50;i++){a*=a;
}

//快速幂写法
int x=2
int n=50;
int ans=1;
while(n){temp=n&1;if(temp){ans*=x;}x*=x;n=n>>1;
}
printf("%d",ans);

快速幂就是将幂数二进制化

然后和1位与，如果得1 最终要输出的结果就乘以当前位的数，否则不乘

之后将幂数左移一位，当前位的数自乘

重复进行操作直到幂数为0结束

看一道具体的题（网址https://leetcode.cn/problems/powx-n/）

题目：实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，x的n次方 ）。

代码如下

//这里的代码是c++语言下的
class Solution {
public:double myPow(double x, int n) {int Bool=0;int Bool2=0;int t=x;if(n==0&&x!=0){return 1;}if(x==0){return 0;}double ans=1;int temp=0;if(n<0){if(n==-2147483648){n=2147483647;Bool2=1;}else{n=abs(n);}Bool=1;}while(n){temp=n&1;if(temp){ans*=x;}x*=x;n=n>>1;}if(Bool2){ans*=t;}if(Bool){ans=1.0/ans;}return ans;}
};