c++ - k 旋转移位数组并找到 x？

Question

我们说一个k-rotated-shifted array，这样的数组可以通过k rotate 进行排序。示例是:A=[10, 15, 20, 1, 7]，k=2。我提出了一种算法，用于在这个 k-rotated-shifted 数组中找到像 x 这样的键。

谁能帮我验证一下？

编辑 1:我的新代码是:

 int S(int l, int r, int x)
{ int f=A[l], m=A[(l+r)/2], la=A[l];
if (x==f or x==m or x==la)
     return 1;
else {if ((x< f and x>m) || (x>f and x>m) || (x<f and x<m))
   return S((l+r)/2, r, x);
   else
    return S(l,(l+r)/2, x);
}
}

Answer 1

中断在 3,4,5,1,2 中找到 1。中断查找不存在的 key ，因为基本情况仅在找到 key 时触发，从而导致无限循环。

要修复，使用条件

first < middle < x or middle < x < first or x < first < middle.

另请注意，如果我们采用 (i + j)/2 的上限，则与 last 进行比较是多余的。