二分查找

说明

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

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

算法的过程如下：

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

下面是一个例子：

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

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

行为

对于各个测试用例，你的解答应该与 Julia 内置的searchsorted函数的行为一致。 也就是说，不要返回你在列表中第一个找到的匹配元素的下标，而要返回一个范围：它的下界是列表中第一个匹配元素的下标，上界是列表中最后一个匹配元素的下标。 不过，为了简化你的解答，你可以假设目标元素不会重复出现，需要处理多重匹配的附加任务测试集除外。

如果要查找的元素不在列表中，你必须返回一个空范围，它的下界是该元素可以插入到这个有序列表中的位置所对应的下标。空范围指的是上界小于下界的范围。

更多细节请阅读searchsorted函数的文档和示例：

searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)

Return the range of indices of a which compare as equal to x (using binary
search) according to the order specified by the by, lt and rev keywords,
assuming that a is already sorted in that order.
Return an empty range located at the insertion point if a does not contain
values equal to x.

See also: insorted, searchsortedfirst, sort, findall.

Examples

julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match
3:3

julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches
4:5

julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
3:2

julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
7:6

julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1:0

附加任务

• 扩展你的解答，支持关键字参数by、lt和rev：by指定应用于列表所有元素的变换，lt指定一种比较方式，rev指定列表是否按相反顺序排列。使用这些参数时，你必须假设列表已经按这些参数排好序。更多细节见sort的文档。
• 支持目标元素重复出现的列表（找出目标元素与之比较相等的第一个和最后一个下标）。

---

来源

Wikipedia