前言
搜索就是在一个已知数组中找到某个数的位置（或者确认是否存在）。本文用C语言描述了线性搜索，二分搜索，和选择排序。举了一些小例子。
线性搜索
基本思想： 遍历每一个数据。找到就返回元素的索引；没找到，就返回 -1 。
main函数
首先，我们看一下 main 函数中的代码
int main(void){
const int MAX = 4;
int a[4] = {1,2,3,4};
int num;
printf("输入要查找的数字:");
scanf("%d",&num);
search(num,a,MAX);
return 0;
}
我们其中的重点就是
search(num,a,MAX);
这是我们自定义的函数。
- 输入：num 需要查找的数字； a 输入的数组； MAX 数组a的大小。
- 输出：如果找到数据，就打印出所在位置索引；如果没找到，就打印出没找到
因此，主程序中，需要定义的变量就用数组a，数组a的大小 MAX （是一个常量），需要查找的数字 num；
num通过 scanf函数，由用户输入。
search函数
search函数是我们自定义的函数，也是程序的主要部分。
void search(int key,int a[],int max){
int res = -1; // 用 res 变量来表达要返回的值
for(int i=0;i<max;i++){
if (a[i] == key){
res = i;
printf("要查找的数字在 %d 位置",res);
break;
}
}
if (res == -1){
printf("要查找的数字不存在");
}
}
注意函数头部分，在参数表中给出数组的时候，不需要给出数组的大小，而需要一个单独的变量来给出函数的大小（具体原因，需要了解指针之后才会清楚）。
void search(int key,int a[],int max)
然后我们需要一个res变量来储存结果。
通过 for 循环来查找
for(int i=0;i<max;i++){
if (a[i] == key){
res = i;
printf("要查找的数字在 %d 位置",res);
break;
}
}
如果找到，就返回位置，并且通过 break 跳出，如果没找到，就继续下一轮循环。
if (res == -1){
printf("要查找的数字不存在");
}
最后的 if 语句判断，如果遍历整个数组还没找到（res == -1），就说明不存在。
一个搜索的例子
问题：美元的钱币上面有面值和对应的名称。例如：1美元对应”penny”。那么，我们应该输入一个面值，就可以得到对应的名称。
注：
面值 名称
1 penny
5 nickel
10 dime
25 quarter
50 half-dollar
想法1：两个数组
# include<stdio.h>
int amount[] = {1,5,10,25,50};
char *name[] = {"penny","nickel","dime","quarter","half-dollar"};//字符指针数组
int search(int key,int a[],int max){
int res = -1; // 用 res 变量来表达要返回的值
for(int i=0;i<max;i++){
if (a[i] == key){
res = i;
break;
}
}
return res;
}
int main(void){
const int MAX = 5;
//int a[4] = {1,2,3,4};
int num;
printf("输入要查找的数字:");
scanf("%d",&num);
int res = search(num,amount,sizeof(amount)/sizeof(amount[0]));
if (res > -1){
printf("金额的面值是：%s",name[res]);
}
return 0;
}
想法2：对应元素进行捆绑
割裂的数组对于 cache 不友好。好的方法是面额和名字绑在一起，离得不远。这需要一种新的数据结构。
# include<stdio.h>
int amount[] = {1,5,10,25,50};
char *name[] = {"penny","nickel","dime","quarter","half-dollar"};
struct{
int amount;
char *name;
}coins[] = {
{1,"penny"},
{5,"nickel"},
{10,"dime"},
{25,"quarter"},
{50,"half-dollar"}
} // 根据 struct 的结构初始化一个数组。
int search(int key,int a[],int max){
int res = -1; // 用 res 变量来表达要返回的值
for(int i=0;i<max;i++){
if (a[i] == key){
res = i;
break;
}
}
return res;
}
int main(void){
const int MAX = 5;
//int a[4] = {1,2,3,4};
int num;
printf("输入要查找的数字:");
scanf("%d",&num);
//int res = search(num,amount,sizeof(amount)/sizeof(amount[0]));
for (int i = 0;i<sizeof(coins)/sizeof(coins[0]);i++)
{
if (num == coins[i].amount){
printf("%s",coins[i].name);
break;
}
}
return 0;
}
二分搜索
线性搜索的缺点：复杂度是 O(n)的，是随数据量线性增加的，效率低。
步骤：
- 数组排序
- 先去找中位数 mid = (left + right) / 2
- a[mid] < k
- left = mid + 1 , 从而排除了左边部分。
- 重复步骤2，直到 ( left = right)
算法复杂度是 O(log
2
n)
search函数的代码
int search(int key, int a[], int len){
int res = -1;
int left = 0;
int right = len - 1;
while (left < right){
mid = (left + right) / 2;
if (a[mid] == k){
res = mid;
break;
}
else if(a[mid] > k){
right = mid - 1;
}
else{
left = mid + 1;
}
}
return res;
}
排序初步-选择排序
二分搜索需要的是有序的数组，因此，这里简略描述一下排序算法。
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
思路：
- 遍历一遍，找出一个最大的数。
int max(int a[],int len){
int maxid = 0; // 最大的值的索引
for (int i = 0; i < len; i++){
printf("执行的i是：%d\n",i);
if (a[i] > a[maxid]){
maxid = i;
}
}
printf("maxid:%d \n",maxid);
return maxid ;
}
- 数组中的最后一个数 和 最大的数做交换
int t = a[maxid];
a[maxid] = a[len-i - 1];
a[len-i -1] = t;
- 然后数组除去最后一个位置的数字以外的其他数字，进行重复步骤1到步骤3的过程。
for(int i = 0; i < len-1; i++ ){
int maxid = max(a,len-i);
printf("a[maxid]:%d \n",a[maxid]);
// swap
int t = a[maxid];
a[maxid] = a[len-i - 1];
a[len-i -1] = t;
}
- 直到进行到只剩下最后一个数字
完整的程序：
// 选择排序
# include <stdio.h>
int max(int a[],int len){
int maxid = 0; // 最大的值的索引
for (int i = 0; i < len; i++){
printf("执行的i是：%d\n",i);
if (a[i] > a[maxid]){
maxid = i;
}
}
printf("maxid:%d \n",maxid);
return maxid ;
}
int main()
{
int a[] = {2,45,6,12,87,34,90,24,23,11,65};
int len = sizeof(a)/sizeof(a[0]);
for(int i = 0; i < len-1; i++ ){
int maxid = max(a,len-i);
printf("a[maxid]:%d \n",a[maxid]);
// swap
int t = a[maxid];
a[maxid] = a[len-i - 1];
a[len-i -1] = t;
}
for(int i =0;i<len;i++){
printf("%d \n",a[i]);
}
return 0;
}