《Unity3D高级编程之进阶主程》第一章，C#要点技术(六) 搜索算法

搜索算法

广度优先搜索和深度优先搜索是最常见的搜索算法，如果不进行些枝剪的话效率是比较差的，直接使用不加修饰的广度和深度算法，会消耗比较多的CPU以至于整体效率比较差。

===

其实搜索算法不只广度和深度优先算法，他们只是明面上看上去比较直接的搜索算法。搜索算法的目的就是找东西，找出各种类型的东西，动态规划，图论，也能帮助我们很好的找到东西。好的搜索算法，大部分需要有数据结构的支撑，在数据结构里记录了信息的特征，前人的搜索的记录，和当前的内容环境，用于枝剪和优化。

搜索的目的一般有，一组元素中找出某元素，一组元素中找出某个特征的所有元素，一个2D或3D空间中找出某元素，2D或3D空间中找出某一个特征的所有元素，以及一堆相互连接的结构中找出两点的最短路径等等等。

二分查找算法

二分查找算法是搜索中用的最多的，也是最简单易用的，效率也比较好的搜索算法。不过它有个前提条件，即查找所用的数组必须是有序的数组。也就是说，在使用二分算法查找前，必须对数组进行排序。而且在每次更改，插入，删除后都要进行排序以保证数组的有序状态。

二分查找算法的步骤是：

1，将数组分为三块，分别是前半部分区域，中间位元素，后半部分区域。

2，将要查找的值和数组的中间位进行比较，若小于中间位则在前半部分查找，若大于中间位则在后半部分查找，如果等于中值时直接返回。

3，继续在选择的查找范围中查找，跳入1步骤，依次进行递归过程，将当前选择的范围继续拆分成前半部分，后半部分，和中间位三部分，直到范围缩小到最小，如果还是没有找到匹配的元素，就说明元素并不在数组里面。

二分查找的平均时间复杂度为O(logN)，是一个效率比较好的查找算法，这也是它常被使用到的原因，不过前提是数组是有序的，可能这对于一些情况下的搜索问题的门槛会比较高，它们可能需要不停得插入或删除元素，这种情况下可以使用二分先查找到插入的位置，再做插入操作，但是插入的操作本身就是O(N)的平均时间复杂度，导致查找无论多快都还是抵不过插入带来的消耗，删除也是同样的道理，数组的拷贝操作已经成了算法中的瓶颈。我们来看看其他搜索算法是怎么做的。

二叉树、二叉查找树、平衡二叉树、红黑树、B树

二叉树及其衍生的所有算法都是以父节点有且只有至多两个子节点为规则。二叉查找树就是在二叉树之上建立的查找树，主要目标是快速查找，它在构造时的特点为，左边的子节点一定比父节点小，右边的子节点一定比父节点大。算法的方式与二分查找算法有点类似，不一样在于二分查找树构建出来的树形结构，由于原始数据的排列不同有可能导致深度很大的二叉树犹如直线连接的节点，因此它也被称为是个不稳定的查找方式，搜索的速度由原始数据的排列方式决定，排列的顺序不好则速度就不佳，因此二叉树的稳定性并不高。

平衡二叉树很好的解决了查找二叉树的二叉树不平衡问题，它的规则是父节点的左右两棵树的深度差的绝对值不能超过1，所有节点都遵循这个规则包括节点下的左右两棵子树叶同样遵循这个规则。二叉树的深度问题解决了，在查找时的效率就更加稳定，如果能一直保持O(logN)的时间复杂度那将是很好的算法效率。

红黑树就是实现平衡二叉树的算法，都是在插入和删除节点操作时通过特定的操作保持二叉查找树的平衡，从而使二叉查找时获得较高的查找效率。它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的，它能够在O(logN)时间复杂度内做查找，插入和删除操作，这里的N为二叉树中元素的数目。

红黑树的数据结构特点是各节点上多了一个颜色值，颜色为红色或黑色。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。具体红黑树是怎样的算法和程序步骤不在这里介绍，有很多书本和资料可供参考。

红黑树虽然高效稳定，但实际项目中运用的稍微少了点，一方面它通常会封装在自定义的底层容器算法中，例如我们通常会重新封装Map、Dictionary容器，把红黑树放入容器中使得写业务逻辑的同学能够不需要关心底层的算法的情况下高效的使用容器。另一方面它的算法复杂度高，一般程序员需要费点心思去研究，因此通常也不会方在明显的位置上使用，这也是红黑树一般都会放入容器里使用的原因之一，它也更适合容器类外壳。还有一方面，查找可以用“快速排序”+“二分查找”代替，效率稍差一些但简单实用，使用优化后的快速排序效率在查找效率上会优于红黑树，如果逻辑中查找的次数远远大于插入与删除的次数，则可以考虑用“快速排序”+“二分查找”代替这种方式进行替代。

B树大家听的也比较多，其实它主要是为磁盘存储设备而设计的一种平衡查找树。它与红黑树主要不同在于，B树是建立在查找树之上的多叉树，它的一个节点上有多个值且父节点可以拥有2个以上的节点，同时还必须保持平衡树的层次结构，即树的深度值不得超过logN的深度(N为节点个数)。这种数据结构犹如在红黑树之上建立多叉的方式，其比较方式由单一值比较改为了多值比较。在B树结构里一个节点里的信息是个数组，它们是有序的，因此可用二分查找法查找数据，若没有找到准确值，则继续往下搜索子节点的数据。B树在游戏项目中里很少用到，不过它在文件信息存储结构上能发挥巨大作用，这也是它被开发出来的原因之一，其他包括B+和B*树都是从B树衍生而来。

四叉树搜索算法

四叉树搜索算法，有点像二叉树的多维度版本，有点类似一维数组上数组分成4块进行查找，但也仅限于此。四叉树的最重要的理念是空间划分，把一个二维空间划分成多个块来存放，它的数据结构也与二叉树一样只是扩展了子节点的个数，每个点有四个子节点，这四个子节点代表父节点的四个象限区块，四个子节点加起来代表整个完整的父节点，以此类推下去，每个节点可以有子节点，一旦有就得四个一起有，除非是末尾的叶子节点，这就相当于是个完美二叉树的变形即完美四叉树，我们可以用一个数组来完美表示完美四叉树的结构情况。

在实际运用中，四叉树主要在2D平面空间上的搜索用的比较多，虽然其他领域也有用到，但平面上空间划分更适合它。我们可以把一个2D矩形平面想象成一个分成相等四个大小的矩形，共有4个子节点共四块矩形方块，其中子节点中即这4块中每块又再次分成相等大小的四块，一直分直到分到定义的最小块为止，最小块大小可自定义，这样的划分将一个大的平面矩形划分成都能用四叉树表示的结构，每一块都有自己的父节点和子节点。

用这样的数据结构表示一个平面里的所有方块内容好处是能牢牢掌控每个小平面内的内容变化。当有元素加入这个平面时，即加入到了这个四叉树的数据结构中去时，会先计算它的坐标在树中的索引，这就相当于在四叉树中搜索某个节点那样，从最大的四块的x、y大小范围开始依次往下推导，一直推导到最小区块的节点上，就能得到该坐标所在的节点。

形成四叉树数据结构后，就可以根据这个数据结构进行查找节点上的元素了。比如在某个位置上可以查找到与它在相同块内的所有其他元素，即给出某个坐标后就能根据四叉树依次推下去最终找到最小块的那个节点，这样就可以获取该块上的所有其他元素的信息。我们可以想象用这种四叉树的方式把地图分成3级，每1级四块矩形图上都存有相关元素的信息，这样就可以快速从1、2、3级地图上得到某块方块内的所有元素的信息。

四叉树在游戏项目中的用法包括，二维平面上的有效碰撞检测搜索范围，地形的有效展示范围，在地图上找某块方块上的人或事，以及包括二维平面的寻路网格构建等。

八叉树搜索算法

八叉树与四叉树类似，但在理念上更关注三维空间上的划分。八叉树把一个立方体从纵向和横向各切一刀，分割成八个相同大小的立方体。每个小立方体也就相当于子节点，也可以再分割成八个相同大小的更小的立方体，用树形结构表示每个大大小小的立方体形成了八叉树。经过树形结构构造八叉树就很容易用在3D空间中的场景管理，可以很快地获取3D场景中的某范围物体，或测试与其它物体是否有碰撞以及是否在可视范围内。八叉树在实际游戏中用到的包括，渲染中的渲染裁切，和物理引擎中的碰撞检测。

优秀的算法都是能找到事物特征并且利用好事物特征的算法，不同种类的算法有其自身的理念，混用或合用几个算法也是常有的事，理解和知晓是第一步，灵活运用真的不是一朝一夕的事。

参考资料

《算法导论》