在二分查找算法前面的還有一個是很一般的查找算法:順序查找.順序查找算法可以用於任何的數組.它對於整個數組是逐個的掃描.可以想像所花的時間.而且順序查找算法比較好理解.所以就不做筆記了.
二分查找算法,說白了點就是把數組砍成兩半.然後你給定一個目標的值.然後算法通過選擇表中的中間點查找.如果你給的數比中間點值小.就在前一半部份查找.大的話就在後一半查找.就是這樣子環循下去.直到找到為此.若一開始就剛剛好.就不用找.帶回家吧.
假設我給的目標值是:MyNum. Array是N個元素的數組.中間點為:Mid.數組的頭與尾分別是:First Last.任務是在Array中找到MyNum.
首先先計算中間點:
Mid=(First+Last)/2;//中間點位置.這裡只是得到下標
Mid_Value=Array[Mid];//這裡才是賦值.
那麼.這樣子的情況下會引發三種可能性:
NO1.
如果你的運氣很好.也許第一次的中間點位置的那個數就是你要找的那個數.
if(Array[Mid]==MyNum)
返回位置;
明白其中的First與First-1.Last-1與Last的區別嗎?不明白話.你得重新看一下數組方面的知識了.
NO2.
大家的運氣都是不一樣的.並不是每個人都會像NO1一樣的運氣.
MyNum小於Mid_Value時候.這時候中間點得變位置了.算法將會在前半部份查找.這時候這部份的范圍變成了[First,Mid],此時還要重新定位Last,將Mid的位置賦給Last.
if(MyNum<Mid_Value)
查找子表Array[First]—Array[Mid-1];
NO3.
還有一種情況:當MyNum>Mid_Value時候.
此時算法將在後子表中查找了.它的范圍變成了: [Mid+1,Last).重新定位First的下標:Mid+1.
if(MyNum>Mid_Value)
定位First到Mid+1;
查找子表Array[Mid+1]—Array[Last-1];
最後,注意兩種情況要中斷查找:
1. 當First與Last交叉時(First>=Last).子表為空.
2. 沒有找到相匹配的值.
二分查找算法的就這樣子了.如果要代碼的話.百度一下.一大堆.主要是理解.多練.
如何計算所花掉的時間?
有很多的朋友都不知道如何計算算法所花掉的時間.當然也沒有辦法進行兩種算法的比較了.這裡我給你一個計時器類的API:
timer();//構造函數,呵呵.構造函數理解了嗎?不理解的話就去看看我前面的文章<構造函數>
void start();//…
void stop();//…
double time() const;//計算時間差,以秒為單位.
用法就這樣子:
…
timer t;
double ResuleTime;
t.start();
…//這裡放上你要測試的時間的代碼就可以了.比如你寫了一個Search()函數.那麼把它放在這裡就可以.了
t.stop();
ResuleTime=t.time();
…
^^ 好用吧..嘿嘿..不用借助其它工具.
本文出自 “雞蛋仔” 博客，謝絕轉載！
