# 二分搜尋法 ## 循序搜尋法 搜尋幾乎是整理資料時一個很重要的步驟，當我們搜集完資料之後，除了計算它們之外，要找出其中的內容也是很常見的應用。當資料不多的時候，只要從第一個位置開始逐一比對，直到找出正確的資料為止，如果是從開始一直比對到最後，直到找到目標資料為止，這種方法我們把它叫做「循序搜尋法」。以下是一個循序搜尋法的例子，先來看執行的影片： {% embed url="" %} 這個程式首先在一開始執行的時候，先加入一個15的數字的清單內容，程式積木如下： ![](https://3758851535-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMo8PFR2UvTkWwSK8m0%2F-LR9cjMSP83DzYVYBWq8%2F-LR9gM46P4KWPvUaGjcI%2F2018-11-13_09-30-41.png?alt=media\&token=d08bc239-4734-4698-b7b8-ea704590817b) 這時候同學們應該知道，在這裡需要建立一個叫做data的清單變數了吧。接著，要開始把這個清單的內容全部都拿出來比較一下，那一定是要另外一個叫做index的變數，然後透過一個指定次數的迴圈，逐一取出資料來比對，程式碼如下： ![](https://3758851535-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMo8PFR2UvTkWwSK8m0%2F-LR9cjMSP83DzYVYBWq8%2F-LR9gqyCkJsLSPWBIBZm%2F2018-11-13_09-32-58.png?alt=media\&token=24431498-8fbd-4f28-8d41-9728b2800a1f) 此種方法的優點就是程式簡單，但缺點則是如果要被搜尋的資料剛好就是在最後面，或是根本就不在清單中，那這個程式就要把所有的資料都比對過一次之後才能夠知道。在清單資料少的時候還算是可以接受，但是如果清單非常大的時候，這樣的方法就顯得非常沒有效率。 不過，在資料沒有排列過任何順序的時候就可以直接使用，也算是一個優點吧。 ## 二分搜尋法 假設資料是有序的，那麼還有一個快速的搜尋方法，也就是在前一個單元中我們讓貓咪猜數字的時候使用的方法，那就是二分搜尋法。每一次都把資料分成兩半，在知道要找的數字比較大或是比較小的時候就可以直接把另外一半不可能的部份排除在搜尋的範圍之外，如此就可以用最快的速度找到資料，或是宣告資料本身是不存在的。 ### 產生有順序的資料 首先，讓我們來產生一組有序的數值資料，程式碼如下： ![](https://3758851535-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMo8PFR2UvTkWwSK8m0%2F-LR9cjMSP83DzYVYBWq8%2F-LR9jN3T20fI3euDOYBk%2F2018-11-13_09-43-51.png?alt=media\&token=b47df5f5-e0c0-484b-9131-94e93a8e7ff7) 不同於上一個程式直接用隨機取數來填入資料，在這裡我們隨機取數用於每一個數值的「增量」。也就是一開始把item這個變數設為1，然後每次都隨機取得1到50之間的一個數字把它加到item變數中，重複15次，每一次取得的新item值就被新增到清單data中，如此就可以取得類隨機的15個遞增的數值了。 ### 二分搜尋原理 有了一個有順序的清單之後，現在我們手上的清單總共有15個數字，其索引值分別也是從1到15，這表示我們要找的數值最小的範圍是1，而最大的範圍是15。一個可能的資料內容如下： ![](https://3758851535-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMo8PFR2UvTkWwSK8m0%2F-LRErQE1AzloiCT_ktVq%2F-LREvlCAdI0Mq6tYw3lH%2F2018-11-14_09-55-50.png?alt=media\&token=68dcec06-e72c-428f-9867-57fbdb62b4d0) 如上面的資料內容所示，所以我們用變數min來記錄1，而max用來記錄15，標示了要搜尋的範圍，那麼中間的索引值target就可以計算如下： $$ target = floor(\frac{min+max}{2}) $$ 其中floor函數是無條件捨去的意思。算出了目標target之後，就依該目標所指向的索引去檢視其中的數字是大於我們要找的數字還是小於我們要找的數字，如果大於的話，就把範圍縮小到左邊，反之則縮小範圍到右側的資料範圍。 例如，以上面的資料內容來看，如果我們要找的數字是28，則在第8個位置的數字是39，它比28還要大，因此我們就要把max指向target-1，如下所示，反之就要把min指向target+1： ![](https://3758851535-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMo8PFR2UvTkWwSK8m0%2F-LRErQE1AzloiCT_ktVq%2F-LRF3N3JKb4XHEYhG_O5%2F2018-11-14_10-33-44.png?alt=media\&token=4be04f7e-a29e-4518-b5ea-a5d68ff98f0f) 接著就可以重新計算target，得到的是4，如下所示： ![](https://3758851535-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMo8PFR2UvTkWwSK8m0%2F-LRErQE1AzloiCT_ktVq%2F-LRF3Za8HJSpiHlVQm0V%2F2018-11-14_10-34-36.png?alt=media\&token=4d6a3bbd-27ee-4588-81aa-eef4672ed083) 此時再比較索引4的內容和28之間的關係，如果不相等的話，再重新設定範圍，直到找到或找不到為止。 ![](https://3758851535-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMo8PFR2UvTkWwSK8m0%2F-LRErQE1AzloiCT_ktVq%2F-LRF3y0e4loxaXz3ABmP%2F2018-11-14_10-36-14.png?alt=media\&token=5f4950d3-d96b-42b1-b761-3f1a7d76ae6f) ![](https://3758851535-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMo8PFR2UvTkWwSK8m0%2F-LRErQE1AzloiCT_ktVq%2F-LRF4NDKkoeIWwdxhCfO%2F2018-11-14_10-38-00.png?alt=media\&token=600dcd3b-8877-4550-ae5e-e8bdee368bb0) ### 二分搜尋程式實作 有了以上的觀念，同學們應該就會知道在程式的進行過程中至少還需要設定min, max, target等 3個變數，以及新增一些比對的過程，我們設計出的積木程式如下： ![](https://3758851535-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMo8PFR2UvTkWwSK8m0%2F-LRErQE1AzloiCT_ktVq%2F-LRF4X0t2OVds5a7-a-E%2F2018-11-14_10-38-51.png?alt=media\&token=6366527c-f5ce-47de-b5ef-66ab84a9aa6b) 值得留意的地方是，在比對的過程中，如果出現了min的數值比max大的情形，那表示在清單中是沒有想要尋找的數值，這是除了找到之外的另外一個結束條件，一定要設定上去，以免程式進入無法結束的狀態喔。 執行過程請參考以下的影片，同學們也可以自行加上暫停時間以觀察變數的變化喔 ： {% embed url="" %}