查找算法篇概括 查找算法的作用

基本概念:在数据集合中寻找满足某种条件的数据元素的过程，称为查找。

查找的结果一般分为两种，一种是查找成功，在数据集合中找到了满足条件的数据元素，二种是查找失败

顺序查找又称线性查找，主要用于在线性表中进行查找线顺序查找，通常分为对一般的无序线性表达顺序查找核对，按关键字有序的顺序表的顺序查找

一般线性表的顺序查找

作为一种最直观的查找方法及基本思想是从线性表的一端开始，逐个检查关键字是否满足给定的条件。如果查找到某个元素的关键字，满足给定条件，则查找成功，返回该元素在线性表中的位置。若已经查找到表的另一端还未发现，查找到符合给定条件的元素，则返回查找失败的信息

用哨兵的目的是Search_Seq循环，不必判断数组是否会越界，因为满足等于零时，循环一定会跳出。需要说明的是，在程序中引入哨兵并不是这个算法独有的,引入哨兵，可以避免很多不必要的判断语句，从而提高程序效率.

其实在空间复杂度上也没有质的改变,再怎么优化都是O(n)

有序表的顺序查找

在查找之前就已经知道表示关键字有序地查找，失败时，可以不用在比较表的另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度

在有序表的顺序查找中，查找成功的平均查找长度和一般线性表的顺序查找。你要查找失败时，查找指针已经走到了某个失败的节点之前。失败节点是我们虚构的空间点，实际上是不存在的，所以到达失败节点时所查找的长度等于它上面一个圆形节点所在层数

折半查找(二分查找)

折半查找:它仅适用于有序的顺序表。

基本思路:首先将定值K与表中中间位置元素的关键字比较，若相等，查找成功，返回该元素的存储位置。若不等，则需查找的元素只能在中间元素以外的前半部分或后半部分，然后再缩小的范围内继续进行同样的查找，如此重复，直到找到为止，或确定表中没有所需要插入的元素，则查找不成功，返回查找失败的信息

因为折半查找需要方便的定位查找区域，所以适合折半查找的存储结构必须具有随机存取的特性，因此，该查找法仅适用于线性表的顺序存储结构，不适合于链式存储结构，先按要求元素，按关键词有序排列

折半查找的判定树一定是平衡二叉树

折半查找一般情况下比顺序查找优秀,但是不是任何情况下都优秀

分块查找(块内无序 块间有序)

分块查找又称索引顺序查找,他吸取了顺序查找和折半查找各自的优点既有动态结构又适用于快速查找.

分块查找的基本思想:是将查找表分为若干子块.块内的元素可以无序，块之间是有序的.第一个块中的最大关键字小于第二块中所有记录的关键词，第二个块中的最大关键词小于第三块中所有记录的关键字，以此类推。在进行一个索引表，索引表中的每个元素，含有各块的最大关键字和各块中第一个元素的地址。索引表按关键字有序排列

算法过程

在索引表中确定待查记录所属的分块(可顺序,可折半)

在块内顺序查找

B树

B树又称多路平衡查找树,B树中所有结点的孩子结点数的最大值，称为B树的阶。通常用M表示，一颗M阶B树或为空树，或为满足如下特性的M叉树:

1)树中每个结点最多有m 棵子树。

2)若根节点不是终端节点，则至少有两棵子树。

3)除根节点外的所有非叶结点至少有M/2棵子树

B树的插入

核心要求:对M阶树----除根节点外,结点关键字个数[m/2]-1<=m-1

子树0=关键字1<关键字1<关键字2<子树2

新元素一定是插入到最底层终端节点，用查找来确定插入位置，再插入Key后，若导致源节点关键字数超过上限，则从中间位置将其关键字分为两部分，总部分包含的关键字放在源节点，右部分包含了关键字，放在新节点中间位置的结点插入源节点的父节点，若此时导致其父节点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致B树高度增I.

B树的删除

在终端结点,直接删除

兄弟够借 若被删除关键词所在节点，删除前关键词个数。且与此节点相应的左右兄弟的结点关键字个数，则需要调整该节点组，由兄弟节点及其双亲结点达到新的平衡

兄弟不够解，若被删除关键字、所在节点删除前的关键字个数，且此时与该节点相邻的左右兄弟的关键词个数，则将关键字删除，或与左右兄弟节点及双亲节中的关键字进行合并

B+树适应数据库所需而出现一种B的变形树。

一颗B+树需满足下列条件:

1)每个分支结点最多有M棵子树，

2)非叶结点至少有两棵子树，其他每个分支结点至少有M/2颗子树。

3)结点的字数个数与关键字个数相等

4)所有叶节点包含全部关键字及指向相应的指针，叶节点中将关键词按大小顺序排列，并且相应节点按大小顺序相互连接起来

5)所有分支结点中仅包含它的各个子节点中关键字的最大实际指向其止节点的指针

B+树的查找、插入和删除操作和B树的基本类似，只是在查找过程中非叶节点上的关键字值等于给定值时，并无终止，而是继续向下查找，直到叶节点上的该关键字为止。所以在B+树中查找时，无论查找成功与否，每次查找都是一条从根节点到叶节点的路径

B树里边这些一个一个的节点，其实是存放在我们的磁盘里边，也就是外存当中，那操作系统，对于磁盘的读写一般是以磁盘块为单位，所以一般来说一加速的一个节点就会存放在某一个磁盘块当中，那所有的这些节点都是存放在不同的磁盘块，因此，我们对这个B+树的查找，其实是这样的过程，我们要从根结点开始查找，那么其实系统在背后做的事情是会找到这个根节点，它到底是存放在哪一个磁盘块当中，比如说存放在这个磁盘块，那么接下来会把这个磁盘块读到内存当中，因为只有把数据读到内存里，计算机才可以来处理查询，这些数据好，把这一块当中之后，接下来我们就可以确定，我们要找的关键字应该要到哪个分支上去找.