二分查找

说明

你的任务是实现一个二分查找算法。

二分查找算法通过在数组中反复对半拆分来查找某一项，每次都只保留包含目标项的那一半。它能让我们快速缩小目标项可能所在的位置，直到找到它，或者排除掉所有可能的位置。

算法的过程如下：

• 找到_有序_数组的中间元素，并把它和我们要找的目标项作比较。
• 如果中间元素就是目标项，那就完成了！
• 如果中间元素大于目标项，就可以排除该元素以及它之后的所有元素。
• 如果中间元素小于目标项，就可以排除该元素以及它之前的所有元素。
• 如果数组中的每个元素都被排除了，说明目标项不在数组中。
• 否则，对数组中还没有被排除的部分重复这个过程。

下面是一个例子：

假设我们要在下面这个有序数组中查找数字 23：[4, 8, 12, 16, 23, 28, 32]。

• 首先，我们把 23 和中间元素 16 作比较。
• 因为 23 大于 16，我们可以排除数组的左半部分，只剩下 [23, 28, 32]。
• 接着，我们把 23 和新的中间元素 28 作比较。
• 因为 23 小于 28，我们可以排除数组的右半部分：[23]。
• 我们找到了目标项。

---

来源

Wikipedia