二分搜尋

說明

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

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

這個演算法的流程如下：

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

來看一個例子：

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

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

例外訊息

有時候，我們會需要引發例外。這麼做的時候，記得一定要附上有意義的錯誤訊息，指出錯誤的來源是什麼。這能讓你的程式碼更容易閱讀，對除錯也有很大的幫助。如果你知道錯誤來源會是某種特定的型別，可以選擇引發其中一種內建的錯誤型別，但仍然要附上有意義的訊息。

這個練習特別要求你，當給定的值無法在陣列中找到時，使用 raise 陳述句來「拋出」一個 ValueError。只有同時raise這個exception並附上訊息，測試才會通過。

若要引發帶有訊息的ValueError，請把訊息寫成exception型別的引數：

# example when value is not found in the array.
raise ValueError("value not in array")

---

出處

Wikipedia