线性搜索
搜索即在一个数组中找到某个数的位置或确定是否存在 线性搜索是最简单的方案，基本方法是遍历。算法如下：
- 设置一个数组，对数组每一个元素进行位置编号
- 用要判断的数字和数组中每一个位置的元素进行比较
- 数字和数组中某一个位置上的数字相等即存在，输出元素位置，不等则输出-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的对数的增长相对很慢，如下表：