CPP学习之——查找数据(14.17-19)

发表于 分类于 ， ， 阅读时长 ≈ 2 分钟

一 概述

本节讲述查找数据的两种方式：递增法和二分查找法 ，然后判断数组是否按照顺序排列

二 递增法查找数据

2.1 查找说明

  • 我们知道数组在内存中是按编号依次排列的，因此只要知道了第一个元素的内存地址， 那么要获取其他元素的地址，只需要在第一个元素的内存地址上进行加减操作就可以
  • 假定我们输入了一个3，那么i的值为3，系统计算出a[3]的值再a[0]的内存地址之后的12个字节(整型变量占用4个字节，3乘以4等于12)，这个地址在变量a中按地址传递给函数，那么函数也就获得了a[3]的内存地址
  • 该例的作用是查找出数据中某个元素的位置并输出该元素的位子编号，也就是下标。由于数组中的元素都是按编号依次排放的，所以我们想要查出某个元素的位置编号，只要从编号为0的元素开始，一个挨一个的检查，直到找出那个元素为止

2.2 代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;
int find(int,int[],int);
int main()
{
	int a[]={44,32,55,64,34,43,22,98};
	cout<<"请输入要查找的数据：";
	int data;
	cin>>data;
	int check=find(data,a,8);
	if(check==-1)
		cout<<"没有查找到数据"<<endl;
	else
		cout<<data<<"在数组a中的位置为："<<check+1<<endl;
	return 0;
}
int find(int m,int a[],int n)
{
	for(int i=0;i<n;i++)
	{
		if(a[i]==m) return i;
	}
	return -1;
}

2.3 输出结果

1
2
请输入要查找的数据：22
22在数组a中的位置为：7

三 二分法查找数据

3.1 查找说明

  • 二分算法的策略是：将一个排好序的数组，不断地分成两半，然后在可能包含我们所要查找的值的那一部分搜索
  • 二分算法在排好序的数组中比递增算法要快速的多，因为假如要对100个数进行查找，递增要进行循环100次，而二分则只需要100为底的2的对数再加1，2的7次方是128，因此最多只需要8次
  • 假如还不明白的话，可以想象一下二分算法是将100个数一分为二，(假定这100个数在数组中的顺序是从小到大)，然后将我们将要查的数据与中间的元素相比较，假如我们的数据小于中间元素，则将查找目标缩定到该数组的前半部分去查找，查找之前先将前半部分一分为二，然后再进行比较，查询数据比中间元素大则将目标锁定后半部分再二分，比它小则锁定到前半部分再二分。依法类推
  • 二分算法的缺点也是显而易见的，假如该数组中有两个或两个以上相同的元素，即两个或两个以上相同的数字，那么二分算法将不能确定该返回哪个值。另外二分算法要求数组必须是排列有序的，否则将会返回一个错误的值

3.2 代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
using namespace std;
int find(int, int[], int);
int main() 
{
	int a[] = { 1, 32, 55, 67, 68, 70, 71, 73, 82, 101, 198, 200, 201 };
	int check=find(70,a,13);
	if(check==-1){cout<<"没有找到数据"<<endl;}
	else
		cout<<"70在数组a中的位置是："<<check+1<<endl;
	return 0;
}
int find(int m, int a[], int n) 
{
	int min = 0, max = n-1, i;
	while (min <= max)
	{
		i = (min + max) / 2;
		if (a[i] == m) {return i;}
		if (a[i] < m) {min = i + 1;} 
		else
			max = i - 1;
	}
	return -1;
}

3.3 输出结果

1
70在数组a中的位置是：6

四 判断数组是否按照顺序排列

4.1 代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
bool add(int [],int);
using namespace std;
int main()
{
	int a[]={22,44,66,88,1,32,64};
	//bool check=add(a,4);
	bool check=add(a,7);
	if(check)
	{
		cout<<"数组a的7个元素是按照从小到大的顺序排列的"<<endl;
		//cout<<"数组a的前4个元素是按照从小到大的顺序排列的"<<endl;
	}
	else
	{
		cout<<"数组a的7个元素不是按照从小到大的顺序排列的"<<endl;
		//cout<<"数组a的前4个元素不是按照从小到大的顺序排列的"<<endl;
	}
	return 0;
}
bool add(int a[],int n)
{
	for(int i=1;i<n;i++)
	{
		if(a[i]<a[i-1])
			return false;
	}
	return true;
}

4.2 输出结果

1
数组a的7个元素不是按照从小到大的顺序排列的