一、顺序搜索法

由于不知道要查找元素的具体位置，只能一个元素一个元素的去判断。

平均查找(n+1)/2

intfind(intarray[],intlength,intvalue)

{

if(NULL==array||0==length)

return-1;

for(intindex=0;index<length;index++){

if(value==array[index])

returnindex;

}

return-1;

}


二、折半查找

对于一个有序数组，我们就可以通过二分查找的方法来提高查找效率。时间复杂度O(lgn)

二分查找有两种写法，需要特别注意边界。

（1）左闭右闭[left,right]

也就是left = 0, right = n-1。这时的判断条件时left < right。并且当去一边的时候要mid+1或mid-1

intsearch(intarray[],intn,intv)

{

intleft,right,middle;

left=0,right=n-1;//左闭右闭

while(left<=right){//循环条件

middle=(left+right)/2;

if(array[middle]>v){

right=middle-1;//由于middle不符合，所有要middle-1满足右闭

}

elseif(array[middle]<v){

left=middle+1;//同上，满足左闭

}

else{

returnmiddle;

}

}

return-1;

}


（2）左闭右开[left,right)


也就是left = 0,right = n。这时不相等时，有left = mid+1 或 right = mid;

intsearch4(intarray[],intn,intv)

{

intleft,right,middle;

left=0,right=n;//左闭右开

while(left<right){//判断条件，由于是开，就必须不能相等

middle=(left+right)/2;

if(array[middle]>v){

right=middle;//满足右开

}

elseif(array[middle]<v){

left=middle+1;//满足左闭

}

else{

returnmiddle;

}

}

return-1;

}


在循环体内,计算中间位置的时候,使用的是这个表达式:


middle=(left+right)/2;


假如,left与right之和超过了所在类型的表示范围的话,那么middle就不会得到正确的值.
所以,更稳妥的做法应该是这样的:

middle=left+(right-left)/2;



三、搜索二叉树

上面的查找是建立在连续内存基础之上的，那么如果是指针类型的数据呢？怎么办呢？那么就需要引入排序二叉树了。排序二叉树的定义很简单：（1）非叶子节点至少一边的分支非NULL；（2）叶子节点左右分支都为NULL；（3）每一个节点记录一个数据，同时左分支的数据都小于右分支的数据。可以看看下面的定义：

typedefstruct_NODE

{

intdata;

struct_NODE*left;

struct_NODE*right;

}NODE;


constNODE*find_data(constNODE*pNode,intdata){

if(NULL==pNode)

returnNULL;

if(data==pNode->data)

returnpNode;

elseif(data<pNode->data)

returnfind_data(pNode->left,data);

else

returnfind_data(pNode->right,data);

}


四、哈希表法-----链式查找，相同映射的，放在一个链表中


我们看到（2）、（3）都是建立在完全排序的基础之上，那么有没有建立在折中基础之上的查找呢？有，那就是哈希表。哈希表的定义如下：1）每个数据按照某种聚类运算归到某一大类，然后所有数据链成一个链表；2）所有链表的头指针形成一个指针数组。这种方法因为不需要完整排序，所以在处理中等规模数据的时候很有效。其中节点的定义如下：

typedefstruct_LINK_NODE

{

intdata;

struct_LINK_NODE*next;

}LINK_NODE;


那么hash表下面的数据怎么查找呢？

LINK_NODE*hash_find(LINK_NODE*array[],intmod,intdata)

{

intindex=data%mod;

if(NULL==array[index])

returnNULL;

LINK_NODE*pLinkNode=array[index];

while(pLinkNode){

if(data==pLinkNode->data)

returnpLinkNode;

pLinkNode=pLinkNode->next;

}

returnpLinkNode;

}


hash表因为不需要排序，只进行简单的归类，在数据查找的时候特别方便。查找时间的大小取决于mod的大小。mod越小，那么hash查找就越接近于普通查找；那么hash越大呢，那么hash一次查找成功的概率就大大增加。