二分搜尋

說明

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

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

這個演算法的流程如下：

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

來看一個例子：

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

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

限制

Rust 的標準函式庫裡已經提供了二分搜尋函式。在這道練習中，你不應該使用這個函式，請改用其他基本工具就好。

加分題

你的測試都通過了嗎？程式碼也寫得夠乾淨嗎？如果願意的話，還有一些額外的事情可以試試看。

• 目前你的 find 函式大概只能用在數字切片上，但 Rust 的型別系統很有彈性，可以寫出一個適用於所有切片的 find 函式，只要切片內的元素可以排序就好。
• 此外，這個 find 函式不只可以用在切片上，還能同時用在 Vec 或 Array 上。

想執行加分題的測試，請移除#[ignore]標記，並以generic feature 執行測試，像這樣：

$ cargo test --features generic

然後請在提交的內容下方留言，分享你的想法。這個實驗讓程式碼變得更好了嗎？還是更糟？你有從中學到什麼嗎？

---

出處

Wikipedia