第七周7.2搜索 课堂学习记录 搜索例子+选择排序+二分搜索《程序设计入门——C语言》第七期 浙江大学 翁恺

1.搜索例子：

#include<iostream>
using namespace std;

/*  美金币值对应的票面名称，给出币值求票面名称
1,	5,	10,	    25,		50
"penny","nickel","dime","quarter","half-dollar"
*/
int search(int key, int arr[], int length)
{
	int i;
	int ret = -1;
	for (i = 0; i < length; i++) {
		if (key == arr[i]) {
			ret = i;
		}
	}
	return ret;
}

int main(){
	int key = 26;
	int a[] = { 1,5,10,25,50 };
	char *name[] = { "penny","nickel","dime","quarter","half-dollar" };
	int j = search(key, a, sizeof(a) / sizeof(a[0]));
	if ( j > -1 )
	{
		printf("%s", name[j]);
	}
	else {
		printf("不存在此面币对应的票面名称！");
	}
	

	printf("\n");
	system("pause");
	return 0;
}

由于分为两个数组存储对cache不友好，故而用结构体对存储结构进行改进（还可以用哈希表）

int a[] = { 1,5,10,25,50 };		//分为两个数组存储对cache不友好
char *name[] = { "penny","nickel","dime","quarter","half-dollar" };

改进后：

#include<iostream>
using namespace std;

/*  美金币值对应的票面名称，给出币值求票面名称
1,	 5,	    10,	  25,	50
"penny","nickel","dime","quarter","half-dollar"
*/

struct {		//用结构体数组存储对cache更友好
	int a;
	char *name;
} coins[] = {
	{1,"penny"},
	{5,"nickel"},
	{10,"dime"},
	{25,"quarter"},
	{50,"half-dollar" }
};

int main(){
	int key = 25;		//要搜索的币值
	int a[] = { 1,5,10,25,50 };		//分为两个数组存储对cache不友好
	char *name[] = { "penny","nickel","dime","quarter","half-dollar" };
	int i;
	for (i = 0; i < sizeof(coins) / sizeof(coins[0]); i++) {
		if (key == coins[i].a) {
			printf("%s", coins[i].name);
			break;
		}
	}

	printf("\n");
	system("pause");
	return 0;
}

2.选择排序+二分搜索：

二分搜索（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search) 。

#include<iostream>
using namespace std;

/*选择排序数组中的数据+二分搜索*/

//二分搜索
int binary_search(int key, int a[], int length);

//求数组中的数据的最大值
int max(int a[], int length);

int main(){
	int a[] = { 5,1,6,2,48,16,95,42,53,10,42,39 };
	int len = sizeof(a) / sizeof(a[0]);
	//选择排序
	for (int i = len - 1; i > 0; i--)
	{
		int maxid = max(a, i + 1);
		//swap a[maxid],a[len-1]
		int t = a[maxid];
		a[maxid] = a[i];
		a[i] = t;
	}
	
	//输出排序后的数据顺序
	for (int i = 0; i < len; i++) {
		printf("%d  ", a[i]);
	}

	printf("\n");

	//开始二分搜索
	int k;
	printf("输入想搜索的数据：");
	scanf("%d", &k);
	int ret = binary_search(k, a, len);

	if (ret > -1) {
		printf("%d", ret);
	}
	else {
		printf("不存在%d", k);
	}
	
	printf("\n");
	system("pause");
	return 0;
}

//二分搜索
int binary_search(int key, int a[], int length)
{
	int ret = -1;
	int left = 0;
	int right = length - 1;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (a[mid] == key) {
			ret = mid;
			break;
		}
		else if (a[mid] > key) {
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}
	return ret;
}

//求数组中的数据的最大值
int max(int a[], int length)
{
	int maxid = 0;
	int i;
	for (i = 1; i < length; i++) {
		if (a[i] > a[maxid]) {
			maxid = i;
		}
	}
	return maxid;
}