二分查找

说明

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

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

算法的过程如下：

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

下面是一个例子：

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

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

限制

Rust 的标准库中已经提供了二分查找函数。这道练习中请不要使用这个函数，只用其他基本工具来实现。

加分项

测试都通过了吗？代码也写得足够干净吗？如果愿意，你还可以再尝试一些额外的内容。

• 目前你的 find 函数可能只适用于数字切片，但 Rust 的类型系统足够灵活，可以写出一个对所有切片都能用的 find 函数，只要切片里的元素可以排序。
• 此外，这个 find 函数不仅可以用在切片上，还能同时用在 Vec 或数组上。

要运行加分测试，请移除#[ignore]标记，并使用generic feature 来执行测试，就像这样：

$ cargo test --features generic

然后请在提交的解答下留言，分享你的想法。这个实验让代码变得更好了吗？还是更糟了？你从中学到了什么吗？

---

来源

Wikipedia