一般来说，如果你希望数据能够被快速的找到，那么最主要的两种技术手段就是二分查找，或者使用Hash函数。

   今天来介绍一个最简单的数据结构，有序数组来组织的二分查找，当然，我的主要目标是介绍前人解决问题的思路，而非算法本身，所以不会尝试用比较难理解的公式和伪码来描述问题。

   使用二分查找的前提条件是：

   1.       数据能够按照某种条件进行排序 ， 比如S={0,1,2,3,4,5,6,7,100,101,102} 就是排好序的数据，左面的数据一定小于右面的。

   2.       可以通过某种方式，取出该数据集中任意子集的中间值。 比如对于S={0,1,2,3,4,5,6,7,100,101,102}，取中值意味着应该取出下标为整数除法 (0+11)/2 = 5 的数字。 如果我们能够快速而直接的取出这个中间值，也就是能够快速的取出下标为5的位置所对应的数据，那么我们就能够进行二分查找。

   下面肯定是一些算法的描述咯。。

   举个例子：

   给定有序结果集S={1对应a,2对应b,3对应c,4对应e,6对应f} ，如果我需要找到4所对应的数据到底是什么，我们应该如何利用二分查找法进行查找呢？

   首先，因为S的总共个数是5，位置从0开始直到4，所以第一次应取的中值是(0+4)/2 = 2

   对应在数组内，应取出的数字是元素[3对应c] ，因为3<4，所以推断数据应该在该元素的右面。于是再从中取中值 (2{原来的中值}+1{右面，所以加1} +4) / 2= 3. 从数组里取出位置3锁对应的数据， 就是4对应e.发现符合要求，于是返回查找成功。

   看起来是挺简单的一个算法，不过，我还是建议大家都自己亲自写一写，因为其实很容易出错~XD。

   看完了算法，也请由我来做一些分析，看看这些算法背后的思路吧。

   在二分查找这套算法中，一个最重要的思路就是，折半查找。 一下排除掉一半的数据，然后再排除一半，再排除一半，直到找到数据为止，说是这样能够快速的找到数据了，为啥就能快呢？

   这就让我想起了一个古老的印度故事，国王要给大臣赢棋的奖赏，大臣希望能够“请在第一个格子里放一颗麦粒，第二个格子里放2颗，第三个格子里放4个，第四个格子里放8粒……依此类推，把64 个格子都放满。” 总共能有多少，结论是一千八百四十四吉六千七百四十四兆零七百三十七亿零九百五十五万一千六百一十五， 二分查找能够在64次运算后处理这样多的记录，结果还是很惊人的，这也就是O(log2N) 时间复杂度的由来，二分查找，2次可以从4条记录中找到对应记录，3次8条，4次16条。。依次类推。

   下面我们来简单的分析一下使用有序数组+二分查找的，他的一些技术特性如何，一般来说，如果你期望快速的了解一款存储产品的性能如何，直接看他选择的映射数据结构，就能大概的猜出这款产品的一些基本特性指标，因为，一个存储的性能好坏，基本不取决于他如何处理分布式场景，而全部取决于如何选择他的映射存储模式。

    不过本周的数据结构因为十分简单，所以一些技术特性也自然的就很简单啦，让我们来看看。

   1.     是否支持范围查找

   基本上来说，这个问题主要取决于两个方面，一个是数据是否有序，另外一个是该存储结构是否提供了快速读取下一个记录的方法。

   对于数组来说，所有数据都是有序的，并且只需要简单地做下标=下标+1的操作，就可以以程序提供的最快方法。因此，范围查找肯定是可以支持的。而且效率应该是很高的 o v 0.

   2.     集合是否能够随着数据的增长而自动扩展

   哎，这个属性是个比较重要的特性，我们来做一下探讨。

   首先，默认的数组是无法支持自动扩展的。

   然后，大家也应该知道，目前在现代语言中，一般都会提供一个支持自由扩展的数组，实现的方式主要是以下这么几类：

   第一类是在在数组的尾部使用连接到另外一个数组的指针。

   第二类是直接创建一个新的数组然后把老数据全部复制过去。

   所以，在有一定的空间消耗的情况下，数组是能够做到自动扩展的~

   然而，虽然能够做到自动的扩展了，但是，要知道，要能够保持映射可以快速的查询，那么必须还要保证新写入的数据的有序性，这就很麻烦了。。因为你无法知道数据写入的顺序，那么如何处理中间值插入就是个很麻烦的问题了。

   比如，如果我的写入顺序是1,3,4,2,5 这个顺序，并且在开始的时候没有办法知道写入的顺序，那么我们唯一能做的事情就是，按照顺序，写1，然后在1的右临位，写3，然后再在右临位写4，这时候来个2，麻烦来了，我应该怎么做呢？

   在数组内，一种最容易想到的方式就是，找到1这个位置，然后将1右边的数据全部往右移动一个位置，然后将2填写进去。

   哈，你也看到了，这种方式会随着我们数据量的变大，而代价变得非常巨大，比如如果有100万行记录，那么就意味着最坏情况下，需要每次写入都移动100万行记录。。。这代价可是真大。

   因此，这也就是我们使用数组的时候的一个最大的问题了，单独的使用数组，是不支持更新的，而使用简单的策略比如自动扩增的数组，也无法支持有序数据的自增的。

   不过，数组作为计算机内的基本数据结构，是其他高级数据结构的基本组成部分，我们后面还会看到他：)

   3.     读写性能如何

   对于读取，如果要快速查找数据，需要使用二分查找来找到一个数据，而二分查找的时间复杂度大概是O(log2N).

   对于写入，数组支持的代价很高，因此基本没人会想要用大数组来做需要频繁增加和删除对应关系的映射的实现的吧？= =

   4.     是否面向磁盘结构

   大部分情况下，纯粹的数组并不是一个面向磁盘的结构。

   磁盘的特性是，一次读取一批数据，或一次写入一批数据时效率会高。

   顺序读大批数据，或者顺序写大批数据的时候，效率会变高。

   而如果要进行二分查找，如果能够一次从磁盘中取出整个数组再进行二分查找，则查找效率会变高，若不得不直接依托磁盘进行二分查找，则读取效率会很低，每次折半，都需要从磁盘中的一个随机位置取出一个block,并从中取出一条记录，随机读取的次数= log2N的结果，而每一次的随机读，对磁盘来说都是灾难。

   不过，在未来，我们会看到一些依托于数组的数据结构，部分的解决了这个问题：)

   5.     并行指标

   只要是不支持修改的数据模型，一般来说并行读取效率都可以做到很高，因为。。完全不会变就不需要加锁啊- -，因此是可以完全并行的

   但并行写入效率嘛。。你能让犀牛飞起来么？

   6.     内存占用

   数组的内存占用应该是个标杆，如果再能比数组更节省空间，那就需要做大量hack和压缩了。

   以上，我们就针对数组，第一次对开篇提到的6个关键的判断指标进行了简单分析，但决定集合的关键，是场景本身，没有银弹，只有最合适的，你们感受一下~

建议继续学习：

1. 为什么数组标号是从0开始的？    (阅读：4951)
2. C语言结构体里的成员数组和指针    (阅读：4861)
3. 将数组定义为常量    (阅读：4569)
4. Tips of Linux C programming    (阅读：3977)
5. xml转数组的方法    (阅读：3500)
6. 数据映射–平衡二叉有序树    (阅读：3445)
7. javascript扩展Array(数组)类    (阅读：3241)
8. 动态数组的 C 实现    (阅读：3116)
9. php数组排序    (阅读：3017)
10. javascript数组排序的问题    (阅读：2957)