● 假設有十個數 6, 11, 13, 15, 18, 24, 32 41, 47及妳/你的學號後兩碼（請排入適當的位置，從小排到大)。
- 第一次：搜尋13，第二次：搜尋29
- 請列出lo, hi和mi的值變化的情形
- 發表一篇文章，標題為:「作業2：二元搜尋法(Binary Search)追蹤<學號> <姓名> 」
第一題：搜尋13
我的學號後兩碼是07
lo =0，0，2，3
mi=4，1，2，3
hi =9，3，3，3
因此種共十個數是分別是
06 07 11 13 15 18 24 32 41 47
第一次搜尋
06 07 11 13 15 18 24 32 41 47
↑ ↑ ↑
lo=0 mi=4 hi=9
13<a[mi]
lo是搜尋的最左邊 hi是搜尋的最右邊
而mi的值是(lo+hi)/2
lo為零 依序 所以hi等於9
mi等於(0+9)/2=4.5←整數 取4 不要有小數點
取第四個就是15
因為第一次搜尋13<15[mi] 因此用公式hi=mi-1
第二次搜尋
06 07 11 13 15 18 24 32 41 47
↑ ↑ ↑
lo=0 mi=1 hi=3
13>a[mi]
因為第一次搜尋13<15[mi] 因此用公式hi=mi-1
因此hi=4-1=3
mi=(0+2)/2=1.5 取1
取第1個數為07
因為第二次搜尋07[mi]<13 因此用公式 lo=mi+1
第三次搜尋
06 07 11 13 15 18 24 32 41 47
↑ ↑
lo=mi=2 hi=3
13>a[mi]
因為第二次搜尋07[mi]<13 因此用公式 lo=mi+1
lo=mi+1 1+1=2 ，hi還是等於3
mi=(2+3)/2=2.5 取2
取第2個數為11
搜尋結果 13>11[mi] 再用公式 lo=mi+1
第四次搜尋
06 07 11 13 15 18 24 32 41 47
↑
lo=mi=hi=3
13=a[mi]
搜尋第三次結果 13>11[mi] 再用公式 lo=mi+1
因此lo=2+1=3 ，hi=3
mi=(3+3)/2=3 取3 lo=mi=hi=3 第3個數為13 得証
第二題：搜尋29
lo =0，5，5，6，7
mi =4，7，5，6，6
hi =9，9，6，6，6
第一次搜尋
06 07 11 13 15 18 24 32 41 47
↑ ↑ ↑
lo=0 mi=4 hi=9
29<a[mi]
lo是搜尋的最左邊 hi是搜尋的最右邊 而mi的值是(lo+hi)/2
lo為零 依序 所以hi等於9 mi等於(0+9)/2=4.5←整數 取4 不要有小數點
取第四個就是15
因為第一次搜尋29>15[mi] 因此用公式lo=mi+1
第二次搜尋
06 07 11 13 15 18 24 32 41 47
↑ ↑ ↑
lo=5 mi=7 hi=9
29<a[mi]
因為第一次搜尋29>15[mi] 因此用公式 lo=mi+1
因此lo=4+1=5 ， hi=9(不變)
mi=(5+9)/2=7
第7個數為32
因為第二次搜尋 32[mi]>29 因此用公式 hi=mi-1
第三次搜尋
6 07 11 13 15 18 24 32 41 47
↑ ↑
lo=mi=5 hi=6
29>a[mi]
因為第二次搜尋32[mi]>29 因此用公式 hi=mi-1
因此用公式 hi=7-1， lo=5(不變)
mi=(5+6)/2=5.5 取5
第5個數為18
因為第三次搜尋 29>18[mi] 因此用公式 lo=mi+1
第四次搜尋
6 07 11 13 15 18 24 32 41 47
↑
lo=mi=hi=6
29>a[mi]
因為第三次搜尋29>18[mi] 因此用公式 lo=mi+1
因此用公式 lo=5+1， hi=6(不變)
mi=(6+6)/2=6
第6個數為24
因為第四次搜尋 29>24[mi] 因此用公式 lo=mi+1
第五次搜尋
06 07 11 13 15 18 24 32 41 47
↑ ↑
hi=mi=6 lo=7
不存在
因為第四次搜尋 29>24[mi] 因此用公式 lo=mi+1
因此用公式 lo=6+1， hi=7(不變)
mi=(7+6)/2=6.5 取6
lo不行比hi大 因此不存在
留言列表
作業 (4)
