数据结构

[Data Structure &Algorithm] 七大查找算法-博客园

http://www.cnblogs.com/maybe2030/p/4715035.html

枚举算法：

也即列举问题的所有状态从而寻找符合问题的解的方法。

适合用于状态较少，比较简单的问题上。

广度优先搜索：

从初始点开始，根据规则展开第一层节点，并检查目标节点是否在这些节点上，若没有，再将所有的第一层的节点逐一展开，得到第二层节点，如没有，则扩展下去，直到发现目标节点为止。

比较适合求最少步骤或最短解序列的题目。

一般设置一个队列queue，将起始节点放入队列中，然后从队列头取出一个节点，检查是否是目标节点，如不是则进行扩展，将扩展出的所有节点放到队尾，然后再从队列头取出一个节点，直至找到目标节点。

深度优先搜索：

一般设置一个栈stack，将起始节点放入栈中，然后从栈中弹出一个节点，检查是否是目标节点，如不是则进行扩展，将扩展出的所有节点入栈，然后再从栈顶弹出一个节点，直到找到目标节点。

深度优先搜索得到的第一个解，不一定是最优解。

双向广度优先搜索：

双向搜索：从起始节点向目标节点方向搜索，同时从目标节点向起始节点方向搜索。

双向搜索只能用于广度优先搜索中。

双向搜索扩展的节点数量要比单向少的多。

A*算法

利用问题的规则和特点来制定一些启发规则，由此来改变节点的扩展顺序，将最有希望扩展出最优解的节点优先扩展，使得尽快找到最优解。

对每一个节点，有一个估价函数F来估算起始节点经过该节点到达目标节点的最佳路径的代价。

每个节点扩展的时候，总是选择具有最小的F的节点。

F=G+B×H：G为从起始节点到当前节点的实际代价，已经算出，H为从该节点到目标节点的最优路径的估计代价。F要单调递增。

B最好随着搜索深度成反比变化，在搜索深度浅的地方，主要让搜索依靠启发信息，尽快的逼近目标，而当搜索深的时候，逐渐变成广度优先搜索。

回溯算法：

和深度优先相似，不同之处在于对一个节点扩展的时候，并不将所有的子节点扩展出来，而只扩展其中的一个。因而具有盲目性，但内存占用少。

搜索中的优化：

在搜索前，根据条件降低搜索规模。

广度优先搜索中，被处理过的节点，充分释放空间。

给据问题的约束条件进行剪枝。

利用搜索过程中的中间解，避免重复计算。

顺序查找

说明：顺序查找适合于存储结构为顺序存储或链接存储的线性表。

基本思想：顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。

复杂度分析：

　　查找成功时的平均查找长度为：（假设每个数据元素的概率相等）ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;

　　当查找不成功时，需要n+1次比较，时间复杂度为O(n);

所以，顺序查找的时间复杂度为O(n)。

顺序查找是在一个已知无(或有序）序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从最后一个开始逐个比较，直到找出与给定关键字相同的数为止，它的缺点是效率低下。

 1.顺序查找：核心：从数据的第一个元素开始，依次比较，直到找到目标数据或查找失败。

1.从表中的第一个元素开始，依次与关键字比较。

2.若某个元素匹配关键字，则 查找成功。

3.若查找到最后一个元素还未匹配关键字，则 查找失败。

2.时间复杂度：顺序查找平均关键字匹配次数为表长的一半，其时间复杂度为O(n)。

3.顺序查找的评估：

顺序查找的优点是对表无要求，插入数据可在O(1)内完成。缺点是时间复杂度较大，数据规模较大时，效率较低。

顺序查找算法

    顺序查找是非常简单常用的查找算法，基本思路：从第一个元素m开始逐个与需要查找的元素x进行比较，当比较到元素值相同(即m=x)时返回元素m的下标，如果比较到最后都没有找到，则返回-1。该算法的时间复杂度为O(n)，如果数据量很大时查找效率会很低。

二分查找算法

    二分查找（又称为折半查找）是在有序序列中查找比较多的查找算法，基本思路：设有一个从小到大的序列，取中间的元素m进行比较，如果等于需要查找的元素x则返回元素m的下标，若x大于m则再从右边的区间查找，若x小于m则再从左边的区间查找，这样每次减少一半的查找范围。时间复杂度为O(lgn)，查找速度相对顺序查找要快很多，但是查找的数据序列必须是有序序列（即数据是从小到大或从大到小排序的）。

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如 果x数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右 半部继续搜索x。

2. 二分查找

说明：元素必须是有序的，如果是无序的则要先进行排序操作。

基本思想：也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

复杂度分析：最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)；

注：折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。——《大话数据结构》

二分查找(binary

search)

二分查找又叫折半查找，要查找的前提是检索结果位于已排序的列表中。

概念

在一个已排序的数组seq中，使用二分查找v，假如这个数组的范围是[low...high]，我们要的v就在这个范围里。查找的方法是拿low到high的正中间的值，我们假设是m，来跟v相比，如果m>v，说明我们要查找的v在前数组seq的前半部，否则就在后半部。无论是在前半部还是后半部，将那部分再次折半查找，重复这个过程，知道查找到v值所在的地方。实现二分查找可以用循环，也可以递归，先给出两种方式的伪代码。

Python版

使用循环实现

def search(seq, v, low, high):

    while low <=high:

        mid= (low + high) // 2

        if v ==seq[mid]:

            returnmid

        elif v >seq[mid]:

            low= mid + 1

        else:

            high= mid - 1

    return None

使用递归实现

def search2(seq, v, low , high):

    if low >high:

        return None

    mid= (low + high) // 2

    if v ==seq[mid]:

        returnmid

    elif v >seq[mid]:

        return search2(seq, v, mid + 1, high)

    else:

        return search2(seq, v, low, mid - 1)