本文共 2686 字，大约阅读时间需要 8 分钟。
一、顺序搜索法
由于不知道要查找元素的具体位置，只能一个元素一个元素的去判断。
平均查找(n+1)/2
int find(int array[], int length, int value){ if(NULL == array || 0 == length) return -1; for(int index = 0; index < length; index++){ if(value == array[index]) return index; } return -1;} 二、折半查找 对于一个有序数组，我们就可以通过二分查找的方法来提高查找效率。时间复杂度O(lgn)
二分查找有两种写法，需要特别注意边界。
（1）左闭右闭[left,right]
也就是left = 0, right = n-1。这时的判断条件时left < right。并且当去一边的时候要mid+1或mid-1
int search(int array[], int n, int v){ int left, right, middle; left = 0, right = n - 1; //左闭右闭 while (left <= right){ //循环条件 middle = (left + right) / 2; if (array[middle] > v){ right = middle - 1; //由于middle不符合，所有要middle-1满足右闭 } else if (array[middle] < v){ left = middle + 1; //同上，满足左闭 } else{ return middle; } } return -1;} （2）左闭右开[left,right) 也就是left = 0,right = n。这时不相等时，有left = mid+1 或 right = mid;
int search3(int array[], int n, int v){ int left, right, middle; left = 0, right = n; //左闭右开 while (left < right){ //判断条件，由于是开，就必须不能相等 middle = (left + right) / 2; if (array[middle] > v){ right = middle; //满足右开 } else if (array[middle] < v){ left = middle + 1; //满足左闭 } else{ return middle; } } return -1;} 在循环体内,计算中间位置的时候,使用的是这个表达式: 三、搜索二叉树
上面的查找是建立在连续内存基础之上的，那么如果是指针类型的数据呢？怎么办呢？那么就需要引入排序二叉树了。排序二叉树的定义很简单：（1）非叶子节点至少一边的分支非NULL；（2）叶子节点左右分支都为NULL；（3）每一个节点记录一个数据，同时左分支的数据都小于右分支的数据。可以看看下面的定义：
typedef struct _NODE{ int data; struct _NODE* left; struct _NODE* right;}NODE; const NODE* find_data(const NODE* pNode, int data){ if(NULL == pNode) return NULL; if(data == pNode->data) return pNode; else if(data < pNode->data) return find_data(pNode->left, data); else return find_data(pNode->right, data); } 四、哈希表法-----链式查找，相同映射的，放在一个链表中 我们看到（2）、（3）都是建立在完全排序的基础之上，那么有没有建立在折中基础之上的查找呢？有，那就是哈希表。哈希表的定义如下：1）每个数据按照某种聚类运算归到某一大类，然后所有数据链成一个链表；2）所有链表的头指针形成一个指针数组。这种方法因为不需要完整排序，所以在处理中等规模数据的时候很有效。其中节点的定义如下：
typedef struct _LINK_NODE{ int data; struct _LINK_NODE* next;}LINK_NODE; 那么hash表下面的数据怎么查找呢？
LINK_NODE* hash_find(LINK_NODE* array[], int mod, int data){ int index = data % mod; if(NULL == array[index]) return NULL; LINK_NODE* pLinkNode = array[index]; while(pLinkNode){ if(data == pLinkNode->data) return pLinkNode; pLinkNode = pLinkNode->next; } return pLinkNode;} hash表因为不需要排序，只进行简单的归类，在数据查找的时候特别方便。查找时间的大小取决于mod的大小。mod越小，那么hash查找就越接近于普通查找；那么hash越大呢，那么hash一次查找成功的概率就大大增加。
最后补充两个有用的查找
平衡树----N层平衡二叉树至少多少个结点？F(N)=F(N-2)+F(N-1)+1
B树
转载地址：http://llryb.baihongyu.com/