在Swift中搜索旋转数组

最近，我发表了有关旋转排序数组的文章。

然后将其旋转k个元素（在以下示例中向左旋转4个）。

蛮力

线性搜索-这将花费O（n）的运行时间，下面是一种可能的实现方式：

简而言之：图形“上升”。

我们的目标数组不这样做，但是：

灰线表示第一个分割。 数组右边大于k的那些元素已被拆分。 我们可以使用此信息执行二进制搜索修改以找到k。

也就是说，如果右边的元素小于当前元素，即nil，则我们位于第k个元素。 我们知道第k个元素是否在当前搜索词的左侧（如果在“行下方”），是否在右边（如果在“行上方”）。

实作

我们可以运行一次简单的二进制搜索两次

显然，如果我们在上半年找到目标，就可以停止。

这是上半部分的示例调用：

binarySearch（arr，14，0，k）

我们可以做得更好吗？

我们不能创建一个自定义的二进制搜索，其中数组的两半不必位于同一物理数组中吗？

我们必须创建映射函数：

我们还需要一个真正的模运算符，例如：

然后，我们可以修改二进制搜索以使用映射和辅助函数：

可以用以下代码调用它，它表示以下有序数组3,5,6,7,9,12,14，该数组在位置4（k）处拆分为7,9,12,14,3,5,6 。 我们可以寻找12，并期望我们的函数返回true。

让 arrMapped = [7,9,12,14,3,5,6]

binarySearchMapped（arr：arrMapped，目标：12，k：4）

我们为什么要这样做？

以这种方式映射二进制搜索是棘手的，但此处显示了对所使用算法的理解。