教學:簡單搜尋

目前沒有人留言
簡單搜尋
二分搜尋演算法(英語: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;
 }  
繼續閱讀較新的文章 繼續閱讀較舊的文章 首頁

歡迎您「化讚為賞 - 回饋創作」

只要您隨手按個讚,我們就會得到實質性的支持!

0 留言:

張貼留言

歡迎您留言,如果有更進一步的問題,也可以 Messenger 聯絡我們喔