二分搜尋

說明

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

二分搜尋演算法會反覆把陣列對半切分，只保留包含目標項目的那一半，藉此在陣列中找到某個項目。 它能讓我們快速縮小目標項目可能所在的位置，直到找到它，或是排除掉所有可能的位置。

這個演算法看起來像這樣：

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

這裡有個例子：

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

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

---

出處

Wikipedia