描述

快速复习这个常见的编程算法。非常适合面试准备。

在这门课上，我将介绍二分搜索算法。我浏览了一些示例并提供了基本的复杂性分析。除了二分搜索，我还解释了下限和上限搜索。你将了解它们是什么以及它们的目的。

项目

我想让你写一个二分搜索函数。选择一种语言并编写一个函数，该函数接受一个值数组和一个要查找的项。该函数返回一个可选值，即找到项的位置的索引，如果没有找到则返回什么。如果不熟悉可选值，如果找不到该值，则返回' -1 '。

在示例Python实现中，签名看起来像这样:

' ' ' py def binary_search(值:ComparableT，项目:Sequence[ComparableT]) ->可选[int]: ' ' '

您应该假设数组已排序。

上下界

为了获得额外的学分，请写出上下界函数。

“lower_bound”返回列表中项目不小于输入值的第一个索引。

“upper_bound”返回列表中项目大于输入值的第一个索引。

对于所有算法，我提供了示例代码的演练。您可以查看代码。

从古到今代码: https://github.com/mortoray/interview.codes/tree/master/binary-search