二分搜尋

說明

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

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

這個演算法的流程如下：

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

來看一個例子：

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

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

---

出處

Wikipedia