《算法笔记》4.5小节——算法初步

算法笔记》4.5小节——算法初步"/>

《算法笔记》4.5小节——算法初步

4.5.1二分法查找
顺序查找->二分查找，时间复杂度从n降到了logn
1.当二分的上界超过Int数据类型的一半，采取mid=left+(right-left)/2来替代表示；
2.二分法可以用递归与非递归两种形式表示
寻找有序序列中是否存在满足某条件的元素
最普通的二分法：

#define _CRT_SECURE_NO_WARNINGS 1
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
//要从递增的序列A[]中查找元素x,查找成功返回元素下标，查找失败则返回-1
int bSearch(int A[],int left,int right,int x) 
{int mid;while (left <= right) {mid = (left + right) / 2;if (A[mid] == x)return mid;else if (A[mid] > x){right = mid - 1;}else{left = mid + 1;}}return -1;
}
int main()
{const int n = 10;int A[n] = { 1,3,4,6,7,8,10,11,12,15 };printf("%d %d",bSearch(A,0,n-1,6), bSearch(A, 0, n - 1, 9));//查找元素6和9return 0;
}

寻找有序序列中第一个满足某条件的元素的位置
见书上P129代码

4.5.2二分法拓展
计算根号2
等价于求某一函数的在某范围内的根
装水问题
木棒切割问题
💠💠💠线段外接圆问题
认为上面的问中都存在函数关系，所以让可以转换为求满足某一条件的长度、水位高度等等。不断逼近这个结果

4.5.3快速幂
1.快速幂的递归写法以及注意事项
2.快速幂的迭代写法以及注意事项
上面两种写法的效率差不多，值得注意的是在判断一个数是不是奇数的时候可以使用if(b&1)来判断，当b是奇数时if条件判断通过，反之，不通过。

问题 A: 找x
问题描述：输入一个数n，然后输入n个数值各不相同，再输入一个值x，输出这个值在这个数组中的下标（从0开始，若不在数组中则输出-1）。

• 输入

测试数据有多组，输入n(1<=n<=200)，接着输入n个数，然后输入x。

• 输出

对于每组输入,请输出结果。

• 样例输入

4
1 2 3 4
3

• 样例输出

2

一开始报错我以为是元素在数组内可能有多个下标，后来发现是这题没说数列有序，排序之后再输出的下标和原来的下标不一样了，所以用结构体存储了元素的值和下标，好麻烦，还不如暴力搜索。

#define _CRT_SECURE_NO_WARNINGS 1
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 210;
struct AA {int yuansu;int xiabiao;
}A[maxn];
bool cmp(AA a, AA b)
{return a.yuansu < b.yuansu;
}
//要从递增的序列A[]中查找元素x,查找成功返回元素下标，查找失败则返回-1
int bSearch(struct AA A[],int left,int right,int x) 
{int mid;while (left <= right) {mid = (left + right) / 2;if (A[mid].yuansu == x){return A[mid].xiabiao;}			else if (A[mid].yuansu > x){right = mid - 1;}else{left = mid + 1;}}return -1;	
}
int main()
{	int n;int i;int x;int num;while (scanf("%d", &n) != EOF){for (i = 0; i < n; i++){scanf("%d",&A[i].yuansu);A[i].xiabiao = i;}sort(A,A+n,cmp);scanf("%d",&x);printf("%d\n",bSearch(A, 0, n - 1, x));//查找元素6和9		}	return 0;
}

问题B：打印极值点下标
问题描述：
在一个整数数组上，对于下标为i的整数，如果它大于所有它相邻的整数，或者小于所有它相邻的整数，则称为该整数为一个极值点，极值点的下标就是i。

• 输入

每个案例的输入如下：有2×n+1行输入：第一行是要处理的数组的个数n；
对其余2×n行，第一行是此数组的元素个数k(4<k<80)，第二行是k个整数，每两个整数之间用空格分隔。

• 输出

每个案例输出不多于n行：每行对应于相应数组的所有极值点下标值，下标值之间用空格分隔，如果没有极值点则不输出任何东西。

• 样例输入

2
4
1 2 1 3
5
3 4 5 6 7

• 样例输出

0 1 2 3
0 4

注意可能有多个案例，其他没什么了

#define _CRT_SECURE_NO_WARNINGS 1
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{int n;int i, j;int k;int a[90];int num;int flag;while (scanf("%d", &n) != EOF){for (i = 0; i < n; i++){num = 0;flag = 0;scanf("%d", &k);for (j = 0; j < k; j++){scanf("%d", &a[j]);}for (j = 0; j < k; j++){if ((j == 0) && (a[j] != a[j + 1]) || (j == k - 1) && (a[j] != a[j - 1]) || (a[j] > a[j - 1]) && (a[j] > a[j + 1]) || (a[j] < a[j - 1]) && (a[j] < a[j + 1])){printf("%d", j); flag = 1;if (j != k - 1)	printf(" ");}}if (flag == 1){printf("\n");}}	}return 0;
}

问题C：查找
问题描述：输入数组长度 n
输入数组 a[1…n]
输入查找个数m
输入查找数字b[1…m]
输出 YES or NO 查找有则YES 否则NO 。

• 输入

输入有多组数据。
每组输入n，然后输入n个整数，再输入m，然后再输入m个整数（1<=m<=n<=100）。

• 输出

如果在n个数组中输出YES否则输出NO。

• 样例输入

6
3 2 5 4 7 8
2
3 6

• 样例输出

YES
NO

典型的二分法

#define _CRT_SECURE_NO_WARNINGS 1
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
//要从递增的序列A[]中查找元素x,查找成功返回元素下标，查找失败则返回-1
int bSearch(int A[], int left, int right, int x)
{int mid;while (left <= right){mid = (left + right) / 2;if (A[mid] == x){return 1;}			else if (A[mid] > x){right = mid - 1;}else{left = mid + 1;}}return 0;
}
int main()
{int n ;int i;int m;int A[100] = {0};int B[100] = { 0 };while (scanf("%d", &n) != EOF){for (i = 0; i < n; i++){scanf("%d",&A[i]);}sort(A, A + n);scanf("%d",&m);for (i = 0; i < m; i++){scanf("%d", &B[i]);if (bSearch(A, 0, n - 1, B[i]))printf("YES\n");elseprintf("NO\n");}return 0;
}