搜索
Suzhou 679 1
线性搜索

搜索即在一个数组中找到某个数的位置或确定是否存在 线性搜索是最简单的方案,基本方法是遍历。算法如下:

  1. 设置一个数组,对数组每一个元素进行位置编号
  2. 用要判断的数字和数组中每一个位置的元素进行比较
  3. 数字和数组中某一个位置上的数字相等即存在,输出元素位置,不等则输出-1,表示不存在
    #include <stdio.h>
    

int search(int key,int a[],int length) //key为要搜索的数字,length为数组长度 { int ret = -1; //ret的值判断是否存在,-1为不存在 int i; for(i = 0;i < length;i++){ if (key == a[i]){ ret = i;
break; } } return ret;
}

int main() { int a[] = {1,3,7,12,19,25,6}; int r = search(12,a,sizeof(a)/sizeof(a[0])); //12为要搜索的数字,sizeof(a)/sizeof(a[0])计算数组长度 printf("%d\n",r); return 0; }

3


Process exited after 0.01273 seconds with return value 0


------------------------------------
###### 搜索举例
美国货币中对于1、5、10、25、50美分,有对应的单词表示,分别为penny、nickel、dime、quarter、half-dollar。要把输入的数字转变成对应的单词,需要有两个数组,把对应位置的元素联系起来。

#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 length) { int ret = -1; int i; for(i = 0;i < length;i++){ if (key == a[i]){ ret = i; break; } } return ret; }

int main() { int k = 10; int r = search(k,amount,sizeof(amount)/sizeof(amount[0])); printf("%s\n",name[r]); return 0; }

dime


Process exited after 0.01262 seconds with return value 0

::: warning
  上述的两个数组是割裂的,对计算机的cache不友好。更好的处理方式是将1和penny放在一起,5和nickel放在一起,即把面额数字和名称单词的更近。 
:::
需要有一个结构把两个数组连结在一起。如下:

#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"}, //将面额和对应字符串放在一起 };

int search(int key,int a[],int length) { int ret = -1; int i; for(i = 0;i < length;i++){ if (key == a[i]){ ret = i; break; } } return ret; }

int main() { int k = 10; int i; for(i = 0;i < sizeof(coins)/sizeof(coins[0]);i++) { if(k == coins[i].amount){ printf("%s\n",coins[i].name); break; } } return 0; }

dime


Process exited after 0.01705 seconds with return value 0

::: tip
上述程序中第35行if(k == coins[i].amount),其中coins[i].amount,表示数组coins中第i个元素中的amount。
数组coins中每一个元素都是由amount面额和name名称两个数组中相同位置的元素组成的,即coins[i]为(amount,name)。
当搜索的数字等于数组coins中的某一个元素中的amount部分的值时,即可判断数组coins中包含该数字,并将该元素的name部分输出。
:::
上述5到10行代码将面额和对应字符串放在一起的写法对cache更为友好。

------------------------------------
###### 二分搜索
线性搜索可能需要完整遍历,毫无效率可言。
为提高搜索效率,提出以下算法:
定义变量k=21,k为要搜索的值。定义数组a,先用一定方式将要执行搜索的数字按照一定规则排好序,如下元素从小到大排序:
|编号|0|1|2|3|4|5|6|7|8|9|
|-|-|-|-|-|-|-|-|-|-|-|
|元素|2|4|9|13|16|21|25|29|32|35|
定义变量left、right分别为第一个编号和最后一个编号的元素,mid为中间编号的数字,即mid=(left+right)/2,由上表可得,mid=(0+9)/2=4,对比a[mid]和k的大小,16<21,可以排除数组中编号0-4的数字,然后对变量left赋值mid+1=5,right不变,继续计算mid=7,a[mid]=29,大于k,排除mid右边编号7-9的数字,left不变,right改为mid-1=6,mid=(5+6)/2=5(**取整数,5和6的区别不大**),a[mid]=21,和k的值相等,即数字21在数组中,位置是6。

int search(int key,int a[],int len) { int ret = -1; //定义表达传递结果的变量ret int left = 0; int right = len-1; //最大下标是长度(个数)-1 while(left < right) * { int mid = (left+right)/2; if(a[mid] == k); //数组a中mid位置的数字和要搜索的数字相等 { ret = mid; //传递出数组中数字位置 break; //跳出循环 }else if ( a[mid] > k){ //数组a中mid位置的数字大于要搜索的数字 right = mid-1; //继续搜索mid左边的数字,重复循环 }else{ //数组a中mid位置的数字小于要搜索的数字 left = mid+1; //继续搜索mid右边的数字,重复循环 } } return ret; //把ret的值返回给主函数 }

::: tip
  上述代码中第六行while循环的条件选择:
算法中搜索结果是数字k在数组a中,如果数字k不在数组a中,如k=22
|0|1|2|3|4|5|6|7|8|9|
|-|-|-|-|-|-|-|-|-|-|
|2|4|9|13|16|21|25|29|32|35|
在不断的二分法计算中,left和right会越来越接近,直到left=right=5,此时的mid=5,mid<k,left=5+1=6,此时left>right,不符合left>right的常理,所以while循环应该在left>right或right<left时停止。
:::
如上代码就是二分搜索,即在每一步将要搜索的目标从中间分成两部分,一半是不符合要求要丢掉的,另一半是符合要求继续搜索的。用二分法在一串数字中搜索某一个数字是否存在,需要log2N次就可以确定(N为数字的数量),当N很大时候,N的对数的增长相对很慢,如下表:![image](https://img-hello-world.oss-cn-beijing.aliyuncs.com/imgs/eb1c5fb17189d86d244342d34586154c.png)
评论区

索引目录