Search in Rotated Sorted Array

Q: Jaka jest złożoność czasowa wyszukiwania w obróconej posortowanej tablicy?

Czas O(log n) i dodatkowa pamięć O(1) . Na każdym kroku zachowywana jest połowa zakresu, więc dla 5000 elementów potrzeba najwyżej 13 kroków. Znalezienie punktu obrotu również zajmuje O(log n) , ale wymaga około dwa razy więcej kroków.

Q: Czy algorytm działa, gdy tablica zawiera duplikaty?

Nie w takiej postaci. Gdy nums[lo] , nums[mid] i nums[hi] są równe, nie można stwierdzić, że któraś z połówek jest posortowana. Zwykle rozwiązuje się to, przesuwając w takim przypadku lo o jeden do przodu, co pozwala zachować poprawność odpowiedzi, ale sprawia, że złożoność w najgorszym przypadku wynosi O(n) .

Q: Czy najpierw znaleźć punkt obrotu, czy szukać w jednym przebiegu?

Obie działają w O(log n) . Najpierw znalezienie minimum dzieli problem na dwa zwykłe wyszukiwania binarne. Wyszukiwanie w jednym przebiegu wykonuje zadanie w pojedynczej pętli, wykonując mniej kroków, i jest wersją, której oczekuje większość osób przeprowadzających rozmowy kwalifikacyjne.

ŚrednieWyszukiwanie binarne

+10

Lista różnych liczb całkowitych została posortowana rosnąco, a następnie obrócona: pewną liczbę elementów, być może zero, przeniesiono z początku na koniec w tej samej kolejności. Na przykład [2, 5, 8, 11, 15, 19, 23] po obróceniu o 4 staje się [15, 19, 23, 2, 5, 8, 11]. Otrzymujesz obróconą listę nums i liczbę całkowitą target. Zwróć indeks target w nums, licząc od 0, lub -1, jeśli tej liczby tam nie ma, w czasie O(log n).

Funkcja

search(nums: integer-array, target: integer) → integer

numsinteger-array: obrócona, posortowana lista różnych liczb całkowitych
targetinteger: wartość, której należy szukać
Zwracainteger: indeks elementu target w nums lub -1, jeśli go brakuje

Ograniczenia

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i], target ≤ 10⁴
Wszystkie wartości w nums są różne.
nums to rosnąca lista obrócona o pewne k, gdzie 0 ≤ k < nums.length; k = 0 oznacza, że pozostaje nieobrócona.

Przykłady

Wejście: nums = [15, 19, 23, 2, 5, 8, 11]target = 5
Wyjście: 4
Wyjaśnienie: Pierwsza środkowa wartość, o indeksie 3, wynosi 2, więc prawa połowa [2, 5, 8, 11] jest posortowana i zawiera 5. Następna środkowa wartość, o indeksie 5, wynosi 8; posortowana lewa część [5, 8] zawiera 5, co prowadzi do indeksu 4.

Wejście: nums = [40, 50, 60, 70, 10, 20, 30]target = 65
Wyjście: -1
Wyjaśnienie: 65 powinno znaleźć się między 60 a 70, ale żaden element go nie zawiera. Pierwszy element środkowy, 70, umieszcza 65 w posortowanej lewej części [40, 50, 60, 70], a zakres stopniowo się tam zawęża, aż będzie pusty.

Wejście: nums = [8, 13, 21, 1, 3, 5]target = 13
Wyjście: 1
Wyjaśnienie: Środkowy element, o indeksie 2, ma wartość 21. Lewa część [8, 13, 21] jest posortowana, a 13 znajduje się między 8 a 21, więc prawa część zostaje odrzucona. Następnie wyszukiwanie znajduje 13 pod indeksem 1.

Pytanie dodatkowe

Jeśli nums może zawierać duplikaty, żaden algorytm nie może zagwarantować O(log n). Czy potrafisz to udowodnić, używając obróconej listy jedynek, w której ukryto pojedyncze zero?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Obrócona posortowana lista składa się z dwóch posortowanych ciągów: [15, 19, 23], a następnie [2, 5, 8, 11]. Porównanie target ze środkową wartością nie mówi już, po której stronie się znajduje. Jednak niezależnie od tego, w którym miejscu podzielisz listę, co najmniej jedna połowa jest posortowana i jedno porównanie pozwala ustalić, czy target może znajdować się w tej połowie.

Skanuj każdy element

Intuicja

Sprawdź każdy indeks i zwróć pierwszy, którego wartość jest równa target, albo -1 po pętli. Odczytuje każdy element, więc działa poprawnie dla każdej listy. Ignoruje dwie posortowane serie: 5000 elementów wymaga do 5000 porównań, podczas gdy wyszukiwanie binarne potrzebuje 13.

Algorytm

Dla każdego indeksu i od 0 do n-1 porównaj nums[i] z target.
Jeśli są równe, zwróć i.
Po pętli zwróć -1.

def search(nums, target):
    for i, value in enumerate(nums):
        if value == target:
            return i
    return -1

Znajdź punkt obrotu, a następnie wyszukaj binarnie

Intuicja

Drugi fragment zaczyna się od najmniejszej wartości; nazwij jego indeks k. Zarówno nums[k..n-1], jak i nums[0..k-1] są posortowane, a każda wartość w pierwszym fragmencie jest większa od każdej wartości w drugim. Gdy znasz k, porównanie target z nums[k] i nums[n-1] pozwala wybrać fragment, a zwykłe wyszukiwanie binarne kończy zadanie.

Aby znaleźć k, porównaj wartość środkową z nums[hi]. Jeśli nums[mid] > nums[hi], wartości gdzieś za mid maleją, więc minimum znajduje się na prawo od niego. W przeciwnym razie nums[mid..hi] rośnie bez spadku, więc minimum znajduje się na pozycji mid lub przed nią. W pierwszym przykładzie środkowe wartości to 2, 19 i 23, co daje k = 3, a 5 znajduje się między nums[3] = 2 i nums[6] = 11. Dwa wyszukiwania binarne wymagają około 2 log2 n kroków.

Algorytm

Ustaw lo = 0 i hi = n-1. Dopóki lo < hi, oblicz mid; jeśli nums[mid] > nums[hi], ustaw lo = mid + 1, w przeciwnym razie ustaw hi = mid.
Końcowy indeks k zawiera najmniejszą wartość.
Jeśli nums[k] ≤ target ≤ nums[n-1], wyszukaj binarnie indeksy od k do n-1; w przeciwnym razie wyszukaj od 0 do k-1.
Zwróć znaleziony indeks lub -1, jeśli zakres się wyczerpie.

def search(nums, target):
    n = len(nums)
    # 1. Find k, the index of the smallest value, where the second run starts.
    lo, hi = 0, n - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1  # the drop is right of mid
        else:
            hi = mid      # mid is in the low run: the minimum is at mid or left of it
    k = lo
    # 2. nums[k..n-1] and nums[0..k-1] are sorted: search the one whose range holds target.
    if nums[k] <= target <= nums[n - 1]:
        lo, hi = k, n - 1
    else:
        lo, hi = 0, k - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Jedno wyszukiwanie binarne w posortowanej połowie

Intuicja

Dotrzymuj obietnicy wyszukiwania binarnego: jeśli target znajduje się na liście, jego indeks leży między lo a hi. Wartości spadają tylko raz w całej liście, więc spadek występuje w co najwyżej jednej z dwóch połówek wokół mid, a druga jest posortowana. Jeśli nums[lo] ≤ nums[mid], lewa połówka jest posortowana; w przeciwnym razie posortowana jest prawa.

W przypadku posortowanej połówki sprawdzenie zakresu na jej obu końcach pozwala ustalić, czy target może się w niej znajdować, na przykład nums[lo] ≤ target < nums[mid] po lewej stronie. Jeśli tak, szukaj tam; jeśli nie, target może znajdować się tylko w drugiej połówce. Każdy krok dzieli zakres na pół: dla 5000 elementów potrzeba co najwyżej 13 kroków.

Algorytm

Ustaw lo = 0 i hi = n-1.
Gdy lo ≤ hi, oblicz mid i zwróć tę wartość, jeśli nums[mid] jest równe target.
Jeśli nums[lo] ≤ nums[mid], lewa połowa jest posortowana: ustaw hi = mid - 1, gdy nums[lo] ≤ target < nums[mid], w przeciwnym razie ustaw lo = mid + 1.
W przeciwnym razie posortowana jest prawa połowa: ustaw lo = mid + 1, gdy nums[mid] < target ≤ nums[hi], w przeciwnym razie ustaw hi = mid - 1.
Gdy pętla się zakończy, zwróć -1.

def search(nums, target):
    lo, hi = 0, len(nums) - 1  # target, if present, sits in nums[lo..hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:
            # nums[lo..mid] is sorted: target is in it only if it fits its range
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            # nums[mid..hi] is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Pułapki i przypadki brzegowe

Zapisywanie nums[lo] < nums[mid] zamiast ≤. Gdy pozostają dwa elementy, mid jest równe lo, a ścisły warunek uznaje [9, 4] za posortowaną prawą połowę: target = 4 zwraca -1.
Porównywanie target z nums[mid] w pierwszej kolejności. W pierwszym przykładzie, gdy target = 19, środkowa wartość 2 jest mniejsza, więc wyszukiwanie przesuwa się w prawo i pomija indeks 1.
Sprawdzanie tylko jednego końca posortowanej połowy. W [40, 50, 60, 70, 80, 10, 20] dla target = 80 sam warunek target ≥ nums[lo] kieruje wyszukiwanie do [40, 50, 60, 70].
W Rust operacja k - 1 na typie usize powoduje niedomiar, gdy k = 0, czyli dla nieobróconej listy. Używaj zakresów półotwartych.
W Lua i R zwracanie pozycji indeksowanej od 1. Odejmij 1.

Najczęstsze pytania3

Jaka jest złożoność czasowa wyszukiwania w obróconej posortowanej tablicy?

Czas O(log n) i dodatkowa pamięć O(1). Na każdym kroku zachowywana jest połowa zakresu, więc dla 5000 elementów potrzeba najwyżej 13 kroków. Znalezienie punktu obrotu również zajmuje O(log n), ale wymaga około dwa razy więcej kroków.

Czy algorytm działa, gdy tablica zawiera duplikaty?

Nie w takiej postaci. Gdy nums[lo], nums[mid] i nums[hi] są równe, nie można stwierdzić, że któraś z połówek jest posortowana. Zwykle rozwiązuje się to, przesuwając w takim przypadku lo o jeden do przodu, co pozwala zachować poprawność odpowiedzi, ale sprawia, że złożoność w najgorszym przypadku wynosi O(n).

Czy najpierw znaleźć punkt obrotu, czy szukać w jednym przebiegu?

Obie działają w O(log n). Najpierw znalezienie minimum dzieli problem na dwa zwykłe wyszukiwania binarne. Wyszukiwanie w jednym przebiegu wykonuje zadanie w pojedynczej pętli, wykonując mniej kroków, i jest wersją, której oczekuje większość osób przeprowadzających rozmowy kwalifikacyjne.

def search(nums, target):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

nums = [15, 19, 23, 2, 5, 8, 11]
target = 5

Oczekiwany wynik

Search in Rotated Sorted Array

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Skanuj każdy element

Znajdź punkt obrotu, a następnie wyszukaj binarnie

Jedno wyszukiwanie binarne w posortowanej połowie

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania