查找，也称为检索，是计算机操作中最普通最费时的操作之一。所谓查找，就是根据给定的值（target），在一个表中查找出等于target的数据元素，若表中有这样的元素，则称查找是成功的，并指出该元素在表中的位置；若表中不存在这样的元素，则称查找是不成功的，或称查找失败，并且给出相应的提示。
在日常生活中，有许许多多查找的实例。如在通讯录中查找某人的地址、电话号码；在书目中查找《数据结构》书等。
本章的主要内容包括：
（1） 线性表的查找List searching
包括两个基本算法，顺序查找Sequential search（包括三种有趣的变异）和二分查找Binary search。
（2）哈希（散列）查找
Hashed list searching—根据数据关键字通过一个算法（哈希函数）计算出所查找数据在表中的位置。
包括哈希函数和处理冲突的方法。
虽然本章讨论的查找算法是在数组结构下进行的，但同样也适用于链表结构。实际上，顺序查找和有序表的顺序查找也是链表中查找数据最通用的方法。二分查找树则是达到二分查找效率的树的结构。这些将在相应的章节中讨论。
注：
关键字(key)：查找通常是按关键字进行的，所谓关键字(key)是数据元素(或记录)中某个数据项的值，用它可以标识(或识别)一个数据元素。例如，一个学生的信息，可以包含：学号、姓名、性别、年龄、家庭住址、电话号码等，都可以作为关键字。在这些关键字中，有些可以唯一标识一个数据元素，而有些则不能唯一标识一个数据元素。如学生信息中，姓名不能唯一标识一个数据元素(因有同名同姓的人)，而学号可以唯一标识一个数据元素(每个学生学号是唯一的，不能相同)。我们将能唯一标识一个数据元素的关键字称为主关键字，而其它关键字称为辅助关键字或从关键字。
代码
#include <stdio.h>
#include <stdlib.h>
#define MAX_KEY 100;
int search1(int k[],int n,int key)
{
int i;
k[n]=key;
for (i=0;key!=k[i];i++)
return i<n?i:-1;
}
int search2(int k[],int n,int key)
{
int i;
k[n]=MAX_KEY;
for (i=0;key>k[i];i++);
if (i<n&&k[i]==key) return i;
return -1;
}
int bin_search(int k[],int n,int key)
{
int low=0,high=n-1,mid;
while (low<=high) {
mid=(low+high)/2;
if (key==k[mid]) return mid;
if (key>k[mid]) low=mid+1;
else high=mid-1;
}
return -1;
}
int ins_search(int k[],int n,int key)
{
int low=0,high=n-1,pos;
while (low<=high) {
pos=(key-k[low])/(k[high]-k[low])*(high-low)+low;
if (key==k[pos]) return pos;
if (key>k[pos]) low=pos+1;
else high=pos-1;
}
return -1;
}
int main(int argc, char *argv[])
{
int a[]={3,4,7,20,45,78,90},i;
i= bin_search(a,7,45);
printf("The n is %d\n",i);
system("PAUSE");
return 0;
}
