六、二分法查找（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，下一篇技術含量要高一點了。