教學:簡單搜尋
簡單搜尋
二分搜尋演算法(英語:binary search algorithm)


在大量資料中,要找到(暴力搜尋)所需之資料是一間非常困難的事,即使有了編號還是很難在龐雜資料堆中找到。

所以搜尋是必要的,以下簡單介紹二分搜。

原理


二分搜也稱折半搜尋演算法,顧名思義,將資料(已排序)不斷拆半、比較、位移直到找到。

  • 舉例:
    • 兩個人玩猜數字遊戲時(1~1000)先猜500,比較大小後如果>500則猜750,反之猜250…以此類推… 

設定


  • 資料分為左端、右端及中端,看成是當一個人再找書的時候,步行的範圍。
    • 備註: 人會不斷走而且走過的路會知道結果,所以左端右端也會動(只找不知道結果的)。
  • 以中端(陣列位置)當成拿起的書。

核心


藉著陣列指位器移動找到要的資料(陣列 [ ] 間的值是種指位器),並節遊不斷移動邊界直到找到所求或者是重疊(代表不存在)

C++程式碼實作


  1. 製造資料、目標
  2. 列一個左端跟右端
  3. 使用 while 迴圈 在不知道第幾次會找到,所設置的條件為 : 左端不等於右端。
  4. 設置中間端,因為不知道中間段在哪,而且中間段(可想成拿起的書)會不斷變化
  5. 比較
  6. 將走過的範圍移除=可走的範圍-已走的=已走的射程端點。在回到第4步驟。 
int a[10]={0,1,2,3,4,5,6,7,8,9},b=3; //step 1
//現在資料跟位置值是一樣的

int left=0,right=9; // step 2

 while(left<right)
 {  //step 3 (left>right 代表無解 )
    int middle=(left+right)/2; //step 4
                
    f(a[middle]>=b)  //step 5
        right=middle;
    else left=middle+1;
 }  
本文採用 BY-NC-NC CC 條款授權,如無特別註明均為原創,轉載請註明出處「杜 靖智 來自 Cotpear」 及本文網址。
本文網址: https://www.cotpear.com/2019/12/blog-post-html-9/
暫無評論

發怖評論 編輯評論


上一篇
下一篇