Искать в Rotated Sorted Array за время 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)

Нужна помощь!

Answer 1

Вот немного другая версия

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

Проверено с этими данными (первый столбец - цель, второй - список, а третий столбец - индекс результата):

  -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) это будет означать, что производительность алгоритма будет линейно уменьшаться с увеличением данных, в то время как в этом случае производительность уменьшается логарифмически с увеличением входных данных, поскольку для каждой итерации мы разделяем набор данных на все меньше и меньше.

Answer 2

Ниже приведен фиксированный код. Я запустил его через leetcode, и он прошел.

Время выполнения: 52 мс, быстрее, чем 11,16% онлайн-заявок на Python для Искать в Rotated Sorted Array. Использование памяти: 11,9 МБ, менее 5,44% сетевых представлений Python для поиска в повернутом отсортированном массиве.

Это O(log n), потому что мы уменьшаем размер проблемы вдвое на каждой итерации. Мы либо выбираем правую половину массива, либо левую половину массива, когда мы перемещаем наш максимум / минимум на каждой итерации.
Таким образом, размер вашего массива уменьшается следующим образом; 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