Board logo

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

作者: 李泳霖    時間: 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/) Powered by Discuz! 7.2