这个问题在这里已有答案：
一个整数排序的数组，由未知的次数向左旋转，编写一个有效的算法来搜索一个元素 .
示例：4 5 6 7 8 9 1 2 3 4
我在想每次在二进制搜索中找到一个mid时我会将元素与极端元素进行比较，然后决定选择哪一半来重复这个过程 . 这是错的吗？还是有任何有效的算法？
您的示例数组包含重复项 . 当存在重复时，没有有效的算法 - 在最坏的情况下，你必须总是做O（n）工作 .
要证明这一点，请考虑以下形式的数组：
000000000000000010000000
它是一个已排序数组的旋转，但在最差的强制转换中，您必须遍历每个元素以查看 1 的位置 .
1
1 回答
您的示例数组包含重复项 . 当存在重复时，没有有效的算法 - 在最坏的情况下，你必须总是做O（n）工作 .
要证明这一点，请考虑以下形式的数组：
它是一个已排序数组的旋转，但在最差的强制转换中，您必须遍历每个元素以查看
1的位置 .