有序数组在数据量较少时候的查找效率比较
笔者曾经参加过某浏览器开发，记得当时在做浏览器放大和缩小的时候，产品经理规定滚动鼠标增加时百分之5,10,15,35,45,50,65,75,85,90,95,100,105,125,150,175,200。当时参加开发的同学就将这组数据做成一个表，然后每次滚动放大或者缩小都首先获取当前数值，然后从这个表中查需要改变多少再设置页面显示。不过查取的时候那位同学采用折半查找方法，认为这样效率很高。
可是事实真的这样吗？
总所周知，对于有序数组的折半查找可以将时间复杂度从顺序查找的N降低到lgN(以2为底)，同时有效提高效率。不过这只是理论值，实际效果如何我们首先来看一组数据。
nKey= 0,递推查找= 234ms,非递推= 188ms,顺序= 31ms nKey= 1,递推查找= 156ms,非递推= 141ms,顺序= 47ms nKey= 2,递推查找= 219ms,非递推= 187ms,顺序= 63ms nKey= 3,递推查找= 281ms,非递推= 249ms,顺序= 93ms nKey= 4,递推查找= 94ms,非递推= 78ms,顺序= 109ms nKey= 5,递推查找= 219ms,非递推= 171ms,顺序= 125ms nKey= 6,递推查找= 156ms,非递推= 125ms,顺序= 140ms nKey= 7,递推查找= 218ms,非递推= 187ms,顺序= 172ms nKey= 8,递推查找= 280ms,非递推= 234ms,顺序= 187ms nKey= 9,递推查找= 359ms,非递推= 266ms,顺序= 499ms（不存在元素) nKey=10,递推查找= 32ms,非递推= 63ms,顺序= 219ms nKey=11,递推查找= 234ms,非递推= 187ms,顺序= 234ms nKey=12,递推查找= 156ms,非递推= 140ms,顺序= 265ms nKey=13,递推查找= 281ms,非递推= 203ms,顺序= 515ms（不存在元素) nKey=14,递推查找= 234ms,非递推= 187ms,顺序= 280ms nKey=15,递推查找= 281ms,非递推= 250ms,顺序= 312ms nKey=16,递推查找= 93ms,非递推= 94ms,顺序= 328ms nKey=17,递推查找= 218ms,非递推= 187ms,顺序= 359ms nKey=18,递推查找= 297ms,非递推= 250ms,顺序= 390ms nKey=19,递推查找= 156ms,非递推= 140ms,顺序= 421ms
这组数据是建立一个0到20的数组，从中拿掉了9和13，然后用0到20分别采用递归二分查找，循环二分查找和直接顺序查找三种方式分别查5000000次得到的毫秒数。但是顺序查找时没有采用辨别从左到右还是从右到左边，以至于后期数值越来越大。但是从中可以看出前一半的成绩顺序查找几乎完胜，而递归查找耗时排名垫底。这是为什么呢?
相信递归查找和循环查找原理不难理解，因为递归的过程中要新开辟内存空间，涉及到大量的压栈和出栈（函数参数+返回地址）操作，当数组很大时会吃掉所有栈空间使得程序崩溃，这也是很多类似嵌入式等内存空间很小的操作系统也或者Windows内核驱动基本不允许使用递归的原因，而循环查找就没有这方面耗时。
1 int BinarySearch(int nArry[],int nLow,int nHigh,int key) 2 { 3 int l=nLow; 4 int r=nHigh; 5 int mid; 6 while (l<=r) 7 { 8 mid=(l+r)/2; 9 if (key==nArry[mid]) 10 return mid; 11 else if(key<nArry[mid]) 12 r=mid-1; 13 else 14 l=mid+1; 15 } 16 return -1; 17 } 18 19 int Search(int key[],int low,int high,int k) 20 { 21 for (int i = low;i <= high;i++) 22 { 23 if (key[i] == k) 24 { 25 return i; 26 } 27 } 28 29 return -1; 30 }
那么非递归的二分查找又为何会败在循序查找手上呢？从源码里面我们可以看出，循环查找一次就是两次比较一处自加，而非递归的二分查找查找一次一次比较，一次相加，一次除法，再比较两次，一次加或者减一。整个过程比起循序查找多出好几个步骤，甚至还有最耗时的除法计算(由于是除以2，编译器一般会转换成移位来提高效率).
所以说二分查找虽说整体效率理论上高，但是每一次查找单元耗时却远比循序查找要大，当数组元素不是太多时效率反而不如循序查找，这也是上面那浏览器放大和缩小我不推荐使用二分查找的原因。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
