Jiang's C++ Space

创作,也是一种学习的过程。

   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::

六、二分法查找(Binary Search)

如何从数组里找一个元素的位置?如果排列是无序的,我们只能从头到尾找,但如果排列是有序的,我们则可以用别的更好的方法,二分查找法就类似我们在英汉词典里找一个单词的方法。如下图所示(假如我们要查找的数字是“88”):

下面我给出了一段demo代码,来演示二分查找法比顺序查找快多少,代码为了方便起见,初始化有序表的时候填入的数字都是均匀的,而事实上数字可以不均匀。你可以调整一下代码中TABLE_SIZE的值,从500,调到5000,再调到10000,再调到30000……你会发觉两者差距越来越明显。我在第一篇的地方提到二分查找法的复杂度为Ο(logn),而顺序查找的复杂度为Ο(n),当n越来越大时候,Ο(logn)的优势也就越来越明显,当然了,前提是“有序”,才可用二分查找法。

#include "stdio.h"
#include 
"time.h"

#define TABLE_SIZE 50000

//returns the position, -1 means failed.
int SequenceSearch(int *pArray, int iArraySize, int iVal)
{
    
int i;
    
for(i=0; i<iArraySize; i++)
    {
        
if(pArray[i]==iVal)
            
return i;
    }

    
return -1;
}

//returns the position, -1 means failed.
int BinarySearch(int *pArray, int iArraySize, int iVal)
{
    
int iLeft = 0;
    
int iRight = iArraySize-1;
    
while(iLeft<=iRight)
    {
        
int iMiddle = (iLeft+iRight)/2;
        
if(iVal < pArray[iMiddle])
        {
            iRight 
= iMiddle-1;
        }
        
else if(iVal > pArray[iMiddle])
        {
            iLeft 
= iMiddle+1;
        }
        
else
            
return iMiddle;
    }

    
return -1;
}

int main(int argc, char* argv[])
{
    
//make the table
    int table[TABLE_SIZE];
    
int i;
    
for(i=0; i<TABLE_SIZE; i++)
    {
        table[i] 
= i*2;
    }

    clock_t ctBegin 
= clock();
    
//Test sequence search
    for(i=0; i<TABLE_SIZE; i++)
    {
        SequenceSearch(table, TABLE_SIZE, i
*2);
    }
    clock_t ctEnd 
= clock();

    printf(
"SequenceSearch takes %d clocks.\n", ctEnd-ctBegin);

    
//Test binary search
    ctBegin = clock();
    
for(i=0; i<TABLE_SIZE; i++)
    {
        BinarySearch(table, TABLE_SIZE, i
*2);
    }
    ctEnd 
= clock();
    
    printf(
"BinarySearch takes %d clocks.\n", ctEnd-ctBegin);

    
return 0;
}

这篇文章是不是太简单了点?OK,下一篇技术含量要高一点了。

posted on 2009-10-15 10:15 Jiang Guogang 阅读(1594) 评论(0)  编辑 收藏 引用 所属分类: Knowledge

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理