2022年图解数据结构-二分法查找法知识 .pdf

六、二分法查找（Binary Search）如何从数组里找一个元素的位置？如果排列是无序的，我们只能从头到尾找，但如果排列是有序的，我们则可以用别的更好的方法，二分查找法就类似我们在英汉词典里找一个单词的方法。如下图所示（假如我们要查找的数字是“88”）：下面我给出了一段demo代码，来演示二分查找法比顺序查找快多少，代码为了方便起见，初始化有序表的时候填入的数字都是均匀的，而事实上数字可以不均匀。你可以调整一下代码中TABLE_SIZE的值，从 500，调到 5000，再调到 10000，再调到 30000 你会发觉两者差距越来越明显。我在第一篇的地方提到二分查找法的复杂度为(logn)，而顺序查找的复杂度名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 4 页 -为(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;iiArraySize;i+)if(pArrayi=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 pArrayiMiddle)名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 4 页 -iLeft=iMiddle+1;elsereturn iMiddle;return-1;int main(int argc,char*argv)/make the table int tableTABLE_SIZE;int i;for(i=0;iTABLE_SIZE;i+)tablei=i*2;clock_t ctBegin=clock();/Test sequence search for(i=0;iTABLE_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;iTABLE_SIZE;i+)名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 4 页 -BinarySearch(table,TABLE_SIZE,i*2);ctEnd=clock();printf(BinarySearch takes%d clocks.n,ctEnd-ctBegin);return 0;这篇文章是不是太简单了点？OK，下一篇技术含量要高一点了。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 4 页 -