在O(log n)时间内搜索旋转排序数组

Question

我在LeetCode上遇到了一个麻烦的问题（搜索旋转排序数组）。

由于某种原因，我的代码总是出现一些问题，所以我不得不查找解决方案。目前我拥有的代码，在查找不存在的目标数字时仍然会无限循环。

我希望能够得到一些帮助，理解是否有更直观的方法来解决这个问题，并帮助修复我的代码。

我认为我不应该需要这一行代码：

if nums[mid] == target or nums[low] == target or nums[high] == target:
            return target

我想知道如何确保我的代码能够在没有指定条件语句的情况下，对于包含1-3个数字的数组找到目标。以下是几个示例：

print(search([1, 2, 3], 1))
print(search([1], 1))
print(search([2, 1], 1))

此外，以这样的示例为例print(search([5, 1, 2, 3, 4], 6))，我的代码从未返回-1。

def search(nums, target):
    low = 0
    high = len(nums)-1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target or nums[low] == target or nums[high] == target:
            return target
        if nums[mid] <= nums[high]:
            if target > nums[mid] and target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1
        elif nums[mid] > nums[low]:
            if target >= nums[low] and target < nums[mid]:
                high = mid - 1
            else:
                low = mid+1
    return -1


print(search([1, 2, 3], 1))
print(search([5, 4, 1, 2, 3], 2))
print(search([3, 4, 5, 1, 2], 2))
print(search([1], 1))
print(search([2, 1], 1))
print(search([5, 1, 2, 3, 4], 6))

我看到许多与上面代码类似的解决方案，人们说它是O(logn)，但是我不理解，因为我们每次只将low和high移动1步。这让我相信该解决方案在最坏情况下是O(n)。

希望能得到一些帮助！

- stillearning

---

我看到的一个问题是，你在应该返回目标的索引时却返回了目标本身。 - andreihondrari

你不是将 low 和 high 向左或向右移动 1 个单位。你是将它们从中间移动 1 个单位（因为你已经测试过 middle 不包含正确的值）。因此，在每一步中，你都会将搜索空间减半，使其成为 O(log n)。 - JohanL

Answer 1

以下是修复后的代码。我在leetcode上运行了它并通过了测试。

运行时间：52毫秒，比Python在线提交的11.16％更快，内存使用率为11.9 MB，低于Python在线提交的5.44％。

这是O(log n)的算法，因为我们每次迭代都将问题规模减半。每次移动high/low时，我们要么选择数组的右半部分，要么选择左半部分。

所以你的数组大小会像这样减少：n，n/2，n/4，...，1，并且需要log n步才能从n减少到1，每次都要将其减半。

class Solution(object):
def search(self, nums, target):
    low = 0
    high = len(nums)-1
    while low <= high:
        mid = (low + high) // 2
        print(low,high,mid)

        if nums[mid] == target:
            return mid
        elif high==low:
            return -1
        elif nums[mid] <= nums[low] and nums[mid] <= nums[high] and nums[mid-1] >= nums[mid]:#mid is pivot

            if target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1
        elif nums[mid] > nums[mid-1] and nums[high] > nums[mid]: #pivot to left of mid\
            if nums[mid] > nums[low]: #pivot at start index

                if target < nums[mid]:
                    high = mid - 1
                else:
                    low = mid + 1
            else:
                if target > nums[mid] and target <= nums[high]:
                    low = mid + 1
                elif target < nums[mid] or target >= nums[low]:
                    high = mid - 1
                else:
                    return -1
        elif nums[mid] >= nums[low] and nums[high] <= nums[mid]: #pivot to right of mid
            if target <= nums[high] or target > nums[mid] :
                low = mid + 1
            else:
                high = mid - 1
        else:
            return -1
    return -1

- hsnsd

Answer 2

这是一个稍微不同的版本，最初的回答。

def search(nums, target):
    low = 0
    high = len(nums)-1

    while low <= high:

        mid = (low + high) // 2

        l = nums[low]
        m = nums[mid]
        h = nums[high]

        if target == l:
            return low

        if target == m:
            return mid

        if target == h:
            return high

        if any([
            l < m < h and target < m,
            l == m < h and target > m,
            l > m < h and target > l and target > m,
            l > m < h and target < l and target < m,
            l < m > h and target > l and target < m
        ]):
            high = mid

        elif any([
            l < m < h and target > m,
            l > m < h and target > m and target < h,
            l < m > h,
        ]):
            low = mid

        elif target < l or target > h:
            break

        elif l == m == h:
            break

        else:
            raise Exception("This is not possible, only if some values are reverse/unordered!")

    return -1

使用以下数据进行测试（第一列为目标，第二列为列表，第三列为结果索引）：

Original Answer：最初的回答

  -10 [1]                      -1
    1 [1]                       0
   22 [1]                      -1
  -10 [1, 2]                   -1
    1 [1, 2]                    0
    2 [1, 2]                    1
   22 [1, 2]                   -1
  -10 [2, 1]                   -1
    1 [2, 1]                    1
    2 [2, 1]                    0
   22 [2, 1]                   -1
  -10 [1, 5]                   -1
    1 [1, 5]                    0
    5 [1, 5]                    1
   22 [1, 5]                   -1
  -10 [5, 1]                   -1
    1 [5, 1]                    1
    5 [5, 1]                    0
   22 [5, 1]                   -1
  -10 [1, 2, 3]                -1
    1 [1, 2, 3]                 0
    2 [1, 2, 3]                 1
    3 [1, 2, 3]                 2
   22 [1, 2, 3]                -1
  -10 [3, 1, 2]                -1
    1 [3, 1, 2]                 1
    2 [3, 1, 2]                 2
    3 [3, 1, 2]                 0
   22 [3, 1, 2]                -1
  -10 [2, 3, 1]                -1
    1 [2, 3, 1]                 2
    2 [2, 3, 1]                 0
    3 [2, 3, 1]                 1
   22 [2, 3, 1]                -1
  -10 [1, 5, 10]               -1
    1 [1, 5, 10]                0
    5 [1, 5, 10]                1
    2 [1, 5, 10]               -1
   10 [1, 5, 10]                2
   22 [1, 5, 10]               -1
  -10 [10, 1, 5]               -1
    1 [10, 1, 5]                1
    5 [10, 1, 5]                2
    2 [1, 5, 10]               -1
   10 [10, 1, 5]                0
   22 [10, 1, 5]               -1
  -10 [5, 10, 1]               -1
    1 [5, 10, 1]                2
    5 [5, 10, 1]                0
    2 [1, 5, 10]               -1
   10 [5, 10, 1]                1
   22 [5, 10, 1]               -1
  -10 [1, 2, 3, 4]             -1
    1 [1, 2, 3, 4]              0
    2 [1, 2, 3, 4]              1
    3 [1, 2, 3, 4]              2
    4 [1, 2, 3, 4]              3
  -10 [1, 2, 3, 4]             -1
  -10 [4, 1, 2, 3]             -1
    1 [4, 1, 2, 3]              1
    2 [4, 1, 2, 3]              2
    3 [4, 1, 2, 3]              3
    4 [4, 1, 2, 3]              0
  -10 [4, 1, 2, 3]             -1
  -10 [3, 4, 1, 2]             -1
    1 [3, 4, 1, 2]              2
    2 [3, 4, 1, 2]              3
    3 [3, 4, 1, 2]              0
    4 [3, 4, 1, 2]              1
  -10 [3, 4, 1, 2]             -1
  -10 [2, 3, 4, 1]             -1
    1 [2, 3, 4, 1]              3
    2 [2, 3, 4, 1]              0
    3 [2, 3, 4, 1]              1
    4 [2, 3, 4, 1]              2
  -10 [2, 3, 4, 1]             -1
  -10 [1, 5, 8, 22]            -1
    1 [1, 5, 8, 22]             0
    5 [1, 5, 8, 22]             1
    8 [1, 5, 8, 22]             2
   22 [1, 5, 8, 22]             3
   10 [1, 5, 8, 22]            -1
  100 [1, 5, 8, 22]            -1
  -10 [22, 1, 5, 8]            -1
    1 [22, 1, 5, 8]             1
    5 [22, 1, 5, 8]             2
    8 [22, 1, 5, 8]             3
   22 [22, 1, 5, 8]             0
   10 [22, 1, 5, 8]            -1
  100 [22, 1, 5, 8]            -1
  -10 [8, 22, 1, 5]            -1
    1 [8, 22, 1, 5]             2
    5 [8, 22, 1, 5]             3
    8 [8, 22, 1, 5]             0
   22 [8, 22, 1, 5]             1
   10 [8, 22, 1, 5]            -1
  100 [8, 22, 1, 5]            -1
  -10 [5, 8, 22, 1]            -1
    1 [5, 8, 22, 1]             3
    5 [5, 8, 22, 1]             0
    8 [5, 8, 22, 1]             1
   22 [5, 8, 22, 1]             2
   10 [5, 8, 22, 1]            -1
  100 [5, 8, 22, 1]            -1
    5 [5, 1, 2, 3, 4]           0
    1 [5, 1, 2, 3, 4]           1
    2 [5, 1, 2, 3, 4]           2
    3 [5, 1, 2, 3, 4]           3
    4 [5, 1, 2, 3, 4]           4
    5 [4, 5, 1, 2, 3]           1
    1 [4, 5, 1, 2, 3]           2
    2 [4, 5, 1, 2, 3]           3
    3 [4, 5, 1, 2, 3]           4
    4 [4, 5, 1, 2, 3]           0
    5 [3, 4, 5, 1, 2]           2
    1 [3, 4, 5, 1, 2]           3
    2 [3, 4, 5, 1, 2]           4
    3 [3, 4, 5, 1, 2]           0
    4 [3, 4, 5, 1, 2]           1
    5 [2, 3, 4, 5, 1]           3
    1 [2, 3, 4, 5, 1]           4
    2 [2, 3, 4, 5, 1]           0
    3 [2, 3, 4, 5, 1]           1
    4 [2, 3, 4, 5, 1]           2
    5 [5, 77, 1, 2, 3]          0
   77 [5, 77, 1, 2, 3]          1
    1 [5, 77, 1, 2, 3]          2
    2 [5, 77, 1, 2, 3]          3
    3 [5, 77, 1, 2, 3]          4
    5 [5, 6, 1, 2, 3]           0
    6 [5, 6, 1, 2, 3]           1
    1 [5, 6, 1, 2, 3]           2
    2 [5, 6, 1, 2, 3]           3
    3 [5, 6, 1, 2, 3]           4
    5 [5, 6, 1, 2, 3, 4]        0
    6 [5, 6, 1, 2, 3, 4]        1
    1 [5, 6, 1, 2, 3, 4]        2
    2 [5, 6, 1, 2, 3, 4]        3
    3 [5, 6, 1, 2, 3, 4]        4
    4 [5, 6, 1, 2, 3, 4]        5

原因并不是O(n)的情况，因为在O(n)的情况下，算法的性能会随着数据量的增加而线性下降，而在这种情况下，随着输入数据的增加，性能以对数方式下降，因为每次迭代我们都将数据集分割成越来越小的部分。"最初的回答"

- andreihondrari

---

会随着数据的增加而“线性增加”，并且会随着输入数据的增加而“对数增加”吗？而不是“减少”？ - stillearning

@user9476376 不，随着数据量的增加，性能总是会降低。想象一下处理10个数字与处理1000000000000000个数字的情况。我正在尝试使用time模块对算法进行测量，但似乎需要大量的数据才能显示几秒钟的时间。我在做这个过程中几次崩溃了我的电脑。 - andreihondrari

print(search([5,6, 1, 2, 3, 4], 6)) 在您的代码中返回-1。@andreihondrari 它应该返回1。 - hsnsd

感谢大家在这个问题上的帮助！ - stillearning

@andreihondrari，如果您不介意我问一下，您制定条件语句的思路是什么？您是如何能够涵盖每种情况的？ - stillearning

@user9476376 我开始通过将可能出现在列表中的各种情况写在纸上，例如：只有一个元素、两个元素、三个元素（在这种情况下，低、中和高是明确的），然后是超过3个元素。之后，我旋转了所有情况，直到得到它们的所有组合。在此之后，我开始建立低/中/高在特定状态下列表应满足的条件，并在代码中构建这些条件，指定何时打破或修改低/中/高。 - andreihondrari