Wyszukiwanie binarne w tablicach obróconych i nieposortowanych
Rozwiążą Państwo zadania search-in-rotated-sorted-array i find-minimum-in-rotated-array, ustalając w każdym kroku, która połowa jest posortowana.
Wyszukiwanie binarne w tablicach obróconych i nieposortowanych to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Czym jest obrócona posortowana tablica
Obrócona posortowana tablica to posortowana tablica, którą przecięto w pewnym punkcie, a następnie zamieniono miejscami powstałe dwie części. Na przykład [4, 5, 6, 7, 0, 1, 2] to posortowana tablica [0,1,2,4,5,6,7] obrócona względem indeksu 4. Standardowe wyszukiwanie binarne nie działa w tym przypadku, ponieważ tablica nie jest już globalnie posortowana.
Kluczowa obserwacja polega na tym, że po dowolnym obrocie co najmniej jedna połowa tablicy jest zawsze posortowana. Przed podjęciem decyzji o przesunięciu granic wyszukiwanie binarne musi ustalić, która połowa jest posortowana.
# A rotated sorted array — one half is always sorted
arr = [4, 5, 6, 7, 0, 1, 2]
# Left half [4,5,6,7] is sorted
# Right half [0,1,2] is also sorted
# But left[0]=4 > right[-1]=2 => rotation happened in left-to-right crossingIdentyfikowanie posortowanej połowy
Po obliczeniu mid należy porównać arr[lo] z arr[mid]. Jeśli arr[lo] <= arr[mid], lewa połowa jest posortowana; w przeciwnym razie posortowana jest prawa połowa. Po ustaleniu, która połowa jest posortowana, można sprawdzić, czy wartość docelowa mieści się w tym posortowanym zakresie, i odpowiednio zawęzić wyszukiwanie.
To drzewo decyzyjne pozwala odrzucić dokładnie połowę tablicy w każdym kroku, zachowując złożoność O(log n) nawet w przypadku obróconej tablicy.
def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
# Left half is sorted
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
# Right half is sorted
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0)) # 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3)) # -1Prześledzenie przykładu
Prześledźmy krok po kroku działanie search_rotated([4,5,6,7,0,1,2], 0). Początkowo lo=0, hi=6, mid=3, arr[mid]=7. Czy wartość docelowa 0 znajduje się w posortowanej lewej połowie [4..7]? Nie, więc ustawiamy lo=4. Teraz lo=4, hi=6, mid=5, arr[mid]=1. Lewa połowa [0,1] jest posortowana (arr[lo]=0 <= arr[mid]=1). Czy 0 należy do [0..1)? Tak, więc ustawiamy hi=4. Teraz lo=4, hi=4, mid=4, arr[4]=0 — znaleziono wartość pod indeksem 4.
# Step-by-step trace
nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
steps = []
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
steps.append(f'lo={lo} hi={hi} mid={mid} val={nums[mid]}')
if nums[mid] == target:
steps.append(f'Found at {mid}')
break
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
for s in steps:
print(s)Obsługa duplikatów podczas obrotu
Gdy obrócona tablica może zawierać duplikaty (np. [1,3,1,1,1]), warunek nums[lo] == nums[mid] jest niejednoznaczny — nie można stwierdzić, która połowa jest posortowana. Bezpieczne rozwiązanie polega na zwiększeniu lo (lub zmniejszeniu hi) o jeden i ponowieniu próby. W najgorszym przypadku złożoność czasowa pogarsza się do O(n), o czym należy wspomnieć podczas rozmowy technicznej.
def search_rotated_with_dups(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return True
# Ambiguous: shrink left boundary
if nums[lo] == nums[mid] == nums[hi]:
lo += 1
hi -= 1
elif nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return False
print(search_rotated_with_dups([1, 3, 1, 1, 1], 3)) # True
print(search_rotated_with_dups([2, 2, 2, 0, 2], 0)) # TrueZnajdowanie minimum w obróconej posortowanej tablicy
Pokrewny problem polega na znalezieniu najmniejszego elementu w obróconej posortowanej tablicy bez wyszukiwania konkretnej wartości docelowej. Minimum zawsze znajduje się w nieposortowanej połowie. W każdym kroku: jeśli arr[mid] > arr[hi], minimum znajduje się w prawej połowie (lo = mid + 1); w przeciwnym razie znajduje się w lewej połowie, włącznie z mid (hi = mid). Gdy lo == hi, minimum zostało znalezione.
def find_min(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # min is in right half
else:
hi = mid # min is at mid or left of mid
return nums[lo]
print(find_min([3, 4, 5, 1, 2])) # 1
print(find_min([4, 5, 6, 7, 0, 1, 2])) # 0
print(find_min([11, 13, 15, 17])) # 11 (no rotation)Dlaczego arr[lo] <= arr[mid] wykrywa posortowaną lewą połowę
Warunek arr[lo] <= arr[mid] działa, ponieważ w posortowanym segmencie (lub segmencie posortowanym bez obrotu) pierwszy element jest zawsze najmniejszy. Jeśli arr[lo] <= arr[mid], w obrębie [lo..mid] nie wystąpił obrót, więc ta połowa jest posortowana. Równość obsługuje przypadek, w którym lo == mid — segment zawierający jeden element jest z definicji posortowany.
Jeśli natomiast arr[lo] > arr[mid], pivot obrotu musi znajdować się między lo i mid, co oznacza, że prawa połowa [mid..hi] jest ciągłym posortowanym segmentem.
# Visualise: detect which half is sorted
examples = [
([4, 5, 6, 7, 0, 1, 2], 0, 6), # mid=3, val=7 => left sorted
([6, 7, 0, 1, 2, 4, 5], 0, 6), # mid=3, val=1 => right sorted
]
for arr, lo, hi in examples:
mid = lo + (hi - lo) // 2
if arr[lo] <= arr[mid]:
print(f'arr[{lo}]={arr[lo]} <= arr[{mid}]={arr[mid]} => LEFT half sorted')
else:
print(f'arr[{lo}]={arr[lo]} > arr[{mid}]={arr[mid]} => RIGHT half sorted')Analiza złożoności
Wyszukiwanie binarne w obróconej posortowanej tablicy nadal ma złożoność czasową O(log n) i pamięciową O(1), ponieważ w każdej iteracji wciąż zmniejszamy przestrzeń wyszukiwania o połowę. Jedyną różnicą w porównaniu z klasycznym wyszukiwaniem binarnym jest dodatkowe sprawdzenie wykonywane w czasie stałym, które pozwala ustalić, która połowa jest posortowana.
W przypadku duplikatów złożoność w najgorszym przypadku pogarsza się do O(n), ponieważ w każdym kroku możemy zwiększyć lo tylko o jeden. Należy wyraźnie wspomnieć o tym kompromisie — pokazuje to, że uwzględniają Państwo przypadki brzegowe wykraczające poza typowy pomyślny przebieg.
Przejście przez LeetCode 33
LeetCode 33 „Wyszukiwanie w obróconej posortowanej tablicy” to kanoniczna postać tego problemu. Ograniczenia gwarantują brak duplikatów i dokładnie jeden obrót. Rozwiązaniem jest funkcja search_rotated, którą napisaliśmy wcześniej. Najważniejsze kwestie podczas rozmowy technicznej: zawsze należy jasno określić założenie o braku duplikatów, zweryfikować nierówności na konkretnym przykładzie obejmującym przypadek brzegowy oraz potwierdzić, że zwracany indeks jest poprawny zarówno dla przypadku znalezienia wartości, jak i jej braku.
# LeetCode 33 — complete solution
def search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]: # left half sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
# Tests
print(search([4,5,6,7,0,1,2], 0)) # 4
print(search([4,5,6,7,0,1,2], 3)) # -1
print(search([1], 0)) # -1LeetCode 153: znajdowanie minimum bez duplikatów
LeetCode 153 „Znajdowanie minimum w obróconej posortowanej tablicy” wymaga znalezienia minimum bez duplikatów. Należy porównać arr[mid] z arr[hi] (a nie z arr[lo]), aby określić, po której stronie znajduje się minimum. Jeśli arr[mid] > arr[hi], minimum znajduje się po prawej; w przeciwnym razie znajduje się w mid lub po lewej stronie. W ten sposób w O(log n) zbiega się do minimum.
def findMin(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
return nums[lo]
print(findMin([3,4,5,1,2])) # 1
print(findMin([4,5,6,7,0,1,2])) # 0
print(findMin([11,13,15,17])) # 11Liczba obrotów i indeks pivota
Gdy można już znaleźć najmniejszy element, znana jest również liczba obrotów: indeks minimum dokładnie odpowiada liczbie pozycji, o które tablica została obrócona w prawo. Na przykład w [4,5,6,7,0,1,2] minimum znajduje się pod indeksem 4, więc tablica została obrócona o 4 pozycje.
Znajomość pivota pozwala zastosować standardowe wyszukiwanie binarne, traktując indeksy modulo n: real_idx = (mid + pivot) % n. To alternatywne sformułowanie może ułatwić rozumowanie podczas pracy ze strukturami indeksowanymi cyklicznie.
def search_via_pivot(nums, target):
n = len(nums)
# Find pivot (index of minimum)
lo, hi = 0, n - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
pivot = lo
# Binary search with offset
lo, hi = 0, n - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
real_mid = (mid + pivot) % n
if nums[real_mid] == target:
return real_mid
elif nums[real_mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(search_via_pivot([4,5,6,7,0,1,2], 0)) # 4Zastosowanie wszystkiego w praktyce
Gdy podczas rozmowy technicznej pojawi się problem dotyczący obróconej tablicy, należy skorzystać z następującego drzewa decyzyjnego. Najpierw trzeba ustalić, czy należy znaleźć wartość docelową, czy znaleźć minimum. W przypadku wyszukiwania wartości docelowej należy zastosować podejście polegające na identyfikacji posortowanej połowy. W przypadku znajdowania minimum należy porównać mid z hi. Jeśli możliwe są duplikaty, należy wspomnieć o złożoności O(n) w najgorszym przypadku i dodać awaryjne zwężanie granic.
Warto przećwiczyć, śledząc działanie kodu dla trzech klasycznych przykładów: bez obrotu, po jednokrotnym obrocie oraz po obrocie umieszczającym minimum na ostatniej pozycji.
Szybki test
Sprawdź swoją znajomość zagadnień Data Structures & Algorithms — Coding Interview Prep omawianych w tej lekcji.
Podsumowanie lekcji
W tej lekcji poznali Państwo następujące zasady: obrócona posortowana tablica zawsze ma co najmniej jedną posortowaną połowę, przed podjęciem decyzji, gdzie kontynuować wyszukiwanie, należy porównać arr[lo] z arr[mid], aby ustalić, która połowa jest posortowana, a znajdowanie minimum polega na porównaniu arr[mid] z arr[hi] w celu zlokalizowania pivota obrotu. W następnej części omówimy warianty wyszukiwania binarnego z dolną i górną granicą.
Często zadawane pytania
Czy lekcja „Wyszukiwanie binarne w tablicach obróconych i nieposortowanych” jest bezpłatna?
Tak — pełny tekst „Wyszukiwanie binarne w tablicach obróconych i nieposortowanych” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Wyszukiwanie binarne w tablicach obróconych i nieposortowanych”?
Rozwiążą Państwo zadania search-in-rotated-sorted-array i find-minimum-in-rotated-array, ustalając w każdym kroku, która połowa jest posortowana. Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Wyszukiwanie binarne w tablicach obróconych i nieposortowanych”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Klasyczne wyszukiwanie binarne: lewo, prawo, środek
- Wyszukiwanie binarne w tablicach obróconych i nieposortowanych
- Dolna i górna granica
- Wyszukiwanie binarne w przestrzeni odpowiedzi