二分查找

说明

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

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

算法的思路是这样的：

• 找到有序数组的中间元素，把它和我们要找的元素进行比较。
• 如果中间元素就是我们要找的元素，那就完成了！
• 如果中间元素大于我们要找的元素，就可以排除这个元素以及它后面的所有元素。
• 如果中间元素小于我们要找的元素，就可以排除这个元素以及它前面的所有元素。
• 如果数组中的每个元素都被排除了，说明要查找的元素不在数组中。
• 否则，在数组中尚未被排除的那一部分重复上述过程。

下面是一个例子：

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

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

---

来源

Wikipedia