二分查找

说明

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

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

算法的过程如下：

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

下面是一个例子：

假设我们要在下面这个有序数组中查找数字 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