種子論壇 | 高雄市資訊培育協會學員討論區

標題: 二分搜尋法 [打印本頁]

作者: 李泳霖 時間: 2021-5-7 14:47 標題: 二分搜尋法

說明
如果搜尋的數列已經有排序，應該儘量利用它們已排序的特性，以減少搜尋比對的次數，這是搜尋的基本原則，二分搜尋法（Binary Search）是這個基本原則的代表。

解法
在二分搜尋法中，從數列的中間開始搜尋，如果這個數小於我們所搜尋的數，由於數列已排序，則該數左邊的數一定都小於要搜尋的對象，所以無需浪費時間在左邊的數；如果搜尋的數大於所搜尋的對象，則右邊的數無需再搜尋，直接搜尋左邊的數。
所以二分搜尋法，就是將數列不斷的分為兩個部份，每次從分割的部份中取中間數比對，反覆這個步驟直到比對成功。

範例
例如要搜尋92於以下的數列，首先中間數索引為(0+9)/2=4（索引由0開始）：
[3 24 57 57 67 68 83 90 92 95]

由於67小於92，所以轉搜尋右邊的數列：
3 24 57 57 67 [68 83 90 92 95]

由於90小於92，再搜尋右邊的數列，這次就找到所要的數了：
3 24 57 57 67 68 83 90 [92 95]

優點
搜尋效率較佳

缺點
資料必須事先排序

二元搜尋法的過程
假設現在有個已排序好的整數陣列，內容如下：

待搜尋的陣列
索引 0 1 2 3 4 5 6 7 8 9
數值 2 9  30  32  38  47  61  69  79  81
然後我們要用二元搜尋法來找到元素69。這邊可以看到此陣列的長度為10，是偶數，所以並不能剛好選到正中間的元素，不過這也沒關係，選擇索引4或是索引5都可以，在此以索引4為例。

      ●                ○                         ●
索引 0 1 2 3 4 5 6 7 8 9
數值 2 9  30  32  38  47  61  69  79  81
                  69 > 38
由於我們要找的元素69比索引4的元素值38還要來得大，因此可以知道若元素值69存在於該陣列的話，那麼它一定是在索引值大於4的位置，索引值小於4的元素們就都不用去管了。所以下一次搜尋，我們要選擇索引5到索引9的中間元素，也就是索引7。

                                 ●       ○       ●
索引 0 1 2 3 4 5 6 7    8 9
數值 2 9  30  32  38  47  61  69  79  81
                              69 == 69
如此一來就找到元素69了，其存在於陣列中的索引7的位置。如何？夠快吧！

二分搜尋法運算思維挑戰題
把小偷揪出來
不好了！一顆價值連城的藍鑽石在展覽時被偷了，但小偷犯了一個錯誤，他用一個外型一樣但廉價的綠鑽石替換
[attach]11787[/attach][attach]11788[/attach][attach]11789[/attach]
已知寶石失竊當天有2000人按照一個接一個的順序進入展示間，因此犯人一定在這2000人當中。警方已掌握了這2000人進入展示間的順序名單，並透過測謊機訊問每人一個問題：「你離開展示間的時候鑽石是藍鑽石還是綠鑽石？」在測謊機的監控下，每個人都會誠實的回答這問題（包括犯人），也就是說，犯人將是離開展示間時，鑽石已是綠鑽石的第一個人！與其一個一個訊問，警方想了一個聰明的方式來減少訊問的人數，以下敘述何者一定是對的?

1.警方一定可以在訊問20人之內揪出小偷。
2. 訊問20人以內不保證能揪出小偷，但是訊問200人以內一定能揪出小偷。
3.警方至少要訊問200人，至多可能要訊問1999人。
4.訊問的人數與運氣有關，如果運氣很差的話，需要訊問全部的人。

歡迎光臨種子論壇 | 高雄市資訊培育協會學員討論區 (http://istak.org.tw/seed/)