外包工

学 JAVA 学 OO

  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  21 随笔 :: 0 文章 :: 0 评论 :: 0 Trackbacks

1     搜尋︰

1.1     循序搜尋(線性搜尋)︰

將資料重頭到尾檢查過一遍,即為循序搜尋。

 

eg.假設有以下十筆資料,欲找數字7

 

1 2 3 4 5 6 7 8 9 10

 

=> 由左至右,共需比對7次。

 

若考慮一般情形的話,循序搜尋N筆資料所須比對的次數最大為N,最小為1,故平均起來需要比對(1+N)/2次。

 

範例程式

 

int data[10]={1,2,3,4,5,6,7,8,9,10};

//target為要找的資料

int target=7;

//found=0為預設值,若找到則將其設為1

int found=0;

for(int i=0;i<10;i++)

  if(target==data[i]){

    found=1;

    printf("found!at %d position\n",i);

  //break可以中斷for迴圈

    break;

}

 

if(found==0)

  printf("not found!\n");

 

 

 

 

1.2     二元搜尋 (Binary Search)

二元搜尋法所使用的時機是當資料以經排好順序後,我們先從中間值開始找起。若目標值比中位數來的小,則往小的另一半繼續找;反之則往大的另一邊找。如此尋找的次數便可有效地降低,最多不會超過log2(N)+1次。

 

eg. 假設有以下10筆資料,欲找數字7,共需比對4次!

 

 

 

 

 

 

 

 

 

1 2 3 4 5 6 7 8 9 10 =>一開始先找中間值5(亦可先找6),未找到。
6 7 8 9 10 =>將範圍縮小成右半邊,再找其中間值8,未找到。
6 7 =>將範圍縮小成左半邊,再找其中間值6,未找到。
7 =>將範圍縮小成右半邊,只剩下7,Bingo找到了!

 

 

 

範例程式

 

int data[10]={1,2,3,4,5,6,7,8,9,10};

//target為要找的資料,found=0為尚未找到,found=1為找到。

int target=7,found=0;

//low為左邊界索引值,high為右邊界索引值,mid為中間值索引值

int low=0,high=9,mid;

//當左邊界小於或等於右邊界 及 尚未找到資料時,重覆執行

while(low <= high && found==0){

    mid=(low+high)/2;

    if(target==data[mid]){

        found=1;

        printf("found!at %d position\n",mid);

    }

    else if(target > data[mid])

        low=mid+1;//重設左邊界

    else if(target < data[mid])

        high=mid-1;//重設右邊界

}

 

if(found==0)

    printf("not found!\n");

 

 

 

 

3     想想看

3.1     若將以上二分搜尋法的程式碼while(low<=high&&found==0)中的low<=high移除,請問執行結果會有何影響?(提示:可分為找到資料與找不到資料兩種狀況來討論)

3.2     請修改以上範例程式碼,使其可以將比對次數印出來。

3.3     想想看:請寫一程式,比較當處理不同的資料數量時(10、100、10000),線性搜尋與二元搜尋法執行的效率。並請將效率量化。

posted on 2010-10-23 09:38 外包工 阅读(308) 评论(0)  编辑  收藏 所属分类: C语言程式设计

只有注册用户登录后才能发表评论。


网站导航: