二分搜尋

說明

你的任務是實作二分搜尋演算法。

二分搜尋演算法會反覆把陣列切成兩半，只留下包含我們要找的項目的那一半，藉此在陣列中找到項目。 它可以讓我們快速縮小項目可能出現的位置，直到找到它，或是排除所有可能的位置。

這個演算法的流程如下：

• 找出_已排序_陣列中間的元素，並拿它和我們要找的項目比較。
• 如果中間的元素就是我們要找的項目，那就完成了！
• 如果中間的元素比我們的項目大，就可以排除那個元素以及它之後的所有元素。
• 如果中間的元素比我們的項目小，就可以排除那個元素以及它之前的所有元素。
• 如果陣列中的每個元素都被排除了，就代表這個項目不在陣列裡。
• 否則，就對陣列中還沒被排除的部分重複同樣的流程。

來看一個例子：

假設我們要在下面這個已排序的陣列中尋找數字 23：[4, 8, 12, 16, 23, 28, 32]。

• 我們先拿 23 和陣列中間的元素 16 比較。
• 因為 23 大於 16，我們可以排除陣列的左半部，剩下 [23, 28, 32]。
• 接著，我們拿 23 和新的中間元素 28 比較。
• 因為 23 小於 28，我們可以排除陣列的右半部：[23]。
• 我們找到目標項目了。

提示

Haskell 支援許多種陣列。這個練習使用的是來自Data.Array的不可變、裝箱且非嚴格的陣列。你可以在下列資源中進一步了解這些陣列的用法：

• A Gentle Introduction to Haskell: Arrays
• Data.Array的文件

作為這個練習的選修延伸，試著讓find函式也能處理邊界任意的陣列，例如第一個索引不一定是 0 的陣列。

---

出處

Wikipedia