查找

 

查找算法最好时间复杂度平均时间复杂度最坏时间复杂度顺序查找O(1)O(n)O(n)二分查找

O(1)

 

O(logn)

插值查找O(1) O(log(n))二叉排序树O(1)O(log(n))O(n)，斜树分块查找  

O(log(m)+N/m)，N个数，m块，二分查找，顺序查找

平衡二叉树（查找，插入，删除） O(log(n))O(log(n))

 

查找：静态查找，动态查找

 

静态查找：

查询某个特定的元素是否在查找表中检索某个特定的数据元素和各种属性

动态查找：

查找时插入数据元素；查找时删除数据元素

一、顺序查找

最简单的查找，按顺序找。序列无序时使用

平均查找次数：(1+n)/2

时间复杂度:

最好，第1次就查找到o(1)；

最差，第n次查找到o(n)；

平均：O(n)

//顺序表查找，成功返回下表，失败返回-1 int SequentialSearch(int *a, int len, int key) { for (int i = 0; i < len; i++) { if (a[i] == key) return i; } return -1; }

 

二、二分查找

 

序列有序时使用，也很简单

时间复杂度：

最好：O(1)

最坏：O(logn)，最坏情况下查找次数：(向下取整logn)+1

//二分查找，折半查找 int BinarySearch(int *a, int len, int key) { int low, mid, high;//不要定义成min,mid,max，不好看 low = 0; high = len - 1; while (low <= high) { mid = (low + high) / 2; if (key == a[mid]) return mid; else if(key > a[mid]) { low = mid + 1; } else { high = mid - 1; } } return -1;//查找失败 }

 

三、插值查找

 

和二分查找差不多，只不过改了一下中间点的位置

以前mid=(low+high)/2=low+(1/2)*(high-low)

现在改为mid=low+(key-a[low])/(high-a[low])*(high-low)，系数(key-a[low])/(high-a[low])是大于0小于1的，当

含义也比较直观，就是当要查找的值较大时，将中点向较大的方向移动一下，减小查找范围，因为要查找的值大概率就在这个范围中。

数据分布均匀的时候效果较好。

时间复杂度和二分查找一样

//插值查找,注意插值查找时，要判断数组是否越界。例如key不在数组范围内，且值非常大时，mid可能越界 int InterpolationSearch(int *a, int len, int key) { int low, mid, high;//不要定义成min,mid,max，不好看 low = 0; high = len - 1; while (low <= high) { mid = low+(high-low)*(key-a[low])/(a[high]-a[low]);//(high-low)放前面，不然变0了。 if (mid >= len || mid < 0)//判断越界 return -1;//越界了 if (key == a[mid]) return mid; else if (key > a[mid]) { low = mid + 1; } else { high = mid - 1; } } return -1;//查找失败 }

四、二叉排序树

二叉排序树(Binary Sort Tree)，又称二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树。

若它的左子树不空，则左子树上所有节点的值都小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值都大于它的根节点的值；它的左、右子树也分别为二叉排序树。

上面就是一棵二叉排序树，当我们对它进行中序遍历时，就可以得到一个有序的序列{35,37,47,51,58,62,73,88,93,99}.

构造一颗二叉排序树，不是为了排序，而是为了提高查找和插入删除关键字的速度。

随便一个二叉排序树的中序遍历都是有序的，二叉排序树构建时随便构建。

二叉排序树的操作主要有：

查找：递归查找是否存在key；插入：原树中不存在key，插入key返回true，否则返回false；构造：循环的插入操作；删除： – 叶子节点：直接删除，不影响原树；

–既有左又有右子树的节点：找到需要删除的节点p的直接前驱或者直接后继s，用s来替换节点p，然后再删除节点s。

//二叉排序树的查找，插入，删除，创建，遍历操作 #include<stdio.h> #define true 1 #define false 0 typedef int bool; typedef struct BTNode { int data; struct BTNode *lchild, *rchild; }BTNode,*BSTree; //查找,查找成功返回该节点的指针，查找失败返回NULL BSTree BSTSearch(BSTree t, int key) { if (!t)//二叉树为空 { return NULL; } else if (key == t->data) { return t; } else if (key > t->data) { return BSTSearch(t->rchild, key); } else { return BSTSearch(t->lchild, key); } } //插入,存在该点就不插入，返回false，不存在该点就插入，返回true bool BSTInsert(BSTree *t, int key) { if (!*t) { *t = (BSTree)malloc(sizeof(BTNode)); (*t)->data = key; (*t)->lchild = (*t)->rchild = NULL; return true; } else if (key > (*t)->data) { return BSTInsert(&(*t)->rchild, key); } else if (key < (*t)->data) { return BSTInsert(&(*t)->lchild, key); } else { return false;//要插入的值本来就在二叉树中 } } //删除某个节点，成功返回true，失败返回false bool BSTDelete(BSTree *t, int key) { if (!*t) { return false; } else if (key == (*t)->data) { return Delete(t); } else if (key < (*t)->data) { return BSTDelete(&(*t)->lchild,key); } else return BSTDelete(&(*t)->rchild,key); } //找到要删除节点的直接前驱，先找到该节点的左孩子，再一路向右到底 bool Delete(BSTree *p) { BSTree q; if (!(*p)->lchild)//左子树为空，则只需要重接它的右子数 { q = *p; *p = (*p)->rchild; free(q); } else if (!(*p)->rchild)//右子树为空，则只需要重接它的左子数 { q = *p; *p = (*p)->lchild; free(q); } else//左右子数均不为空 { q = *p; BSTree s = q->lchild; while (s->rchild)//转左，然后向右到尽头 { q = s; s = s->rchild; } q->data = s->data;//s指向被删节点的直接前驱 if (q != *p) { q->rchild = s->lchild;//重接q的右子树 } else if (q == *p) { q->lchild = s->lchild;//重接q的左子树 } free(s); } return true; } //创建二叉排序树,安装中序遍历的顺序创建 void BSTCreate(BSTree *t) { int a[10] = { 62,88,58,47,35,73,51,99,37,93 };//中序遍历顺序 for (int i = 0; i < 10; i++) { BSTInsert(t, a[i]); } } //中序遍历 void InOrderTraverse(BSTree t) { if (!t) { return; } InOrderTraverse(t->lchild); printf("%d ",t->data); InOrderTraverse(t->rchild); } int main(void) { BSTree t = NULL; //创建二叉排序树 BSTCreate(&t); //遍历二叉排序树 printf("初始二叉树:\n"); InOrderTraverse(t); BSTree b = BSTSearch(t, 99); printf("\n查找99:\n"); printf("查找到的值为%d\n", b->data); //插入100， BSTInsert(&t, 63); printf("插入88之后，二叉排序树中序遍历结果为:\n"); InOrderTraverse(t); //删除88 BSTDelete(&t, 62); printf("\n删除62之后，二叉排序树中序遍历结果为：\n"); InOrderTraverse(t); return 0; }

 

时间复杂度：

 

最好：O(1)

最坏：O(n)，斜树

一般：O(logn)：二叉树比较平衡的时候

五、索引查找

索引分为线性索引，树型索引，多级索引。跟操作系统中一样

线性索引：稠密索引，分块索引，倒排索引

1.稠密索引

数据集中每条记录对应一个索引项，索引项是有序的。这样可以对索引项进行折半，插值，斐波那契查找等。

2.分块索引

就像图书馆中的书摆放一样

块间有序：后面一块所有记录的关键字要大于前一块关键字的最大值。。。

块内无序：快内不要求有序，不然代价太大。

3.倒排索引

正常查找：从记录中查找有没有某个关键字

倒排索引：根据关键字，查找包含该关键字的记录，就比如百度搜索东西。