Binær søgning i roterede og usorterede arrays
Løs search-in-rotated-sorted-array og find-minimum-in-rotated-array ved at afgøre, hvilken halvdel der er sorteret i hvert trin.
Binær søgning i roterede og usorterede arrays er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 2 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i DSA Interview Prep, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Hvad er et roteret sorteret array?
Et roteret sorteret array er et sorteret array, der er blevet delt ved et drejepunkt, hvorefter de to dele er byttet om. For eksempel er [4, 5, 6, 7, 0, 1, 2] det sorterede array [0,1,2,4,5,6,7] roteret ved indeks 4. Standardversionen af binær søgning fejler her, fordi arrayet ikke længere er globalt sorteret.
Den centrale pointe er, at mindst den ene halvdel af arrayet altid er sorteret efter en rotation. Din binære søgning skal identificere, hvilken halvdel der er sorteret, før du beslutter, hvor grænserne skal flyttes.
# 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 crossingIdentificering af den sorterede halvdel
Efter beregning af mid skal du sammenligne arr[lo] med arr[mid]. Hvis arr[lo] <= arr[mid], er den venstre halvdel sorteret; ellers er den højre halvdel sorteret. Når du ved, hvilken halvdel der er sorteret, kan du kontrollere, om målet ligger inden for det sorterede interval, og derefter indsnævre søgningen.
Dette beslutningstræ lader dig kassere præcis halvdelen af arrayet pr. trin, så kompleksiteten O(log n) bevares, selv i et roteret array.
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)) # -1Gennemgang af et eksempel
Lad os gennemgå search_rotated([4,5,6,7,0,1,2], 0) trin for trin. Til at begynde med er lo=0, hi=6, mid=3, arr[mid]=7. Ligger målet 0 i den sorterede venstre halvdel [4..7]? Nej, så flytter vi lo=4. Nu er lo=4, hi=6, mid=5, arr[mid]=1. Den venstre halvdel [0,1] er sorteret (arr[lo]=0 <= arr[mid]=1). Ligger 0 i [0..1)? Ja, så sætter vi hi=4. Nu er lo=4, hi=4, mid=4, arr[4]=0 — fundet på indeks 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)Håndtering af dubletter ved rotation
Når det roterede array kan indeholde dubletter (f.eks. [1,3,1,1,1]), er betingelsen nums[lo] == nums[mid] tvetydig — du kan ikke afgøre, hvilken halvdel der er sorteret. Den sikre løsning er at øge lo (eller sænke hi) med én og prøve igen. Det forringer tidskompleksiteten i værste fald til O(n), og det bør du nævne for intervieweren.
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)) # TrueFind minimum i roteret sorteret array
Et beslægtet problem går ud på at finde minimumselementet i et roteret sorteret array uden at søge efter et bestemt mål. Minimum findes altid i den usorterede halvdel. Ved hvert trin gælder følgende: Hvis arr[mid] > arr[hi], ligger minimum i den højre halvdel (lo = mid + 1); ellers ligger det i den venstre halvdel inklusive midtpunktet (hi = mid). Når lo == hi, har du fundet minimum.
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)Hvorfor arr[lo] <= arr[mid] finder den sorterede venstre halvdel
Betingelsen arr[lo] <= arr[mid] virker, fordi det første element i et sorteret segment (eller et sorteret segment uden rotation) altid er det mindste. Hvis arr[lo] <= arr[mid], skete der ingen rotation inden for [lo..mid], så den halvdel er sorteret. Ligheden håndterer tilfældet, hvor lo == mid (et segment med ét element er trivielt sorteret).
Omvendt, hvis arr[lo] > arr[mid], må rotationsdrejepunktet ligge mellem lo og mid, hvilket betyder, at den højre halvdel [mid..hi] er det sammenhængende sorterede segment.
# 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')Kompleksitetsanalyse
Søgning i et roteret sorteret array med binær søgning har stadig tidskompleksiteten O(log n) og pladskompleksiteten O(1), fordi vi stadig halverer søgeområdet ved hver gentagelse. Den eneste forskel fra klassisk binær søgning er et ekstra tjek med konstant tidskompleksitet for at identificere, hvilken halvdel der er sorteret.
Med dubletter forringes kompleksiteten i værste fald til O(n), fordi vi kun kan øge lo med én ved hvert trin. Nævn denne afvejning eksplicit — det viser, at du tænker på kanttilfælde ud over det normale forløb.
Gennemgang af LeetCode 33
LeetCode 33 'Søgning i roteret sorteret array' er den kanoniske udgave af dette problem. Begrænsningerne garanterer ingen dubletter og præcis én rotation. Løsningen er funktionen search_rotated, som vi skrev tidligere. Vigtige pointer til interviewet: Angiv altid antagelsen om ingen dubletter, kontrollér dine uligheder med et konkret eksempel ved grænsen, og bekræft, at det returnerede indeks er korrekt, både når målet findes, og når det ikke findes.
# 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: Find minimum uden dubletter
LeetCode 153 'Find minimum i roteret sorteret array' beder dig finde minimum uden dubletter. Tilgangen er at sammenligne arr[mid] med arr[hi] (ikke arr[lo]) for at afgøre, hvilken side minimum ligger på. Hvis arr[mid] > arr[hi], ligger minimum til højre; ellers ligger det ved mid eller til venstre. Dette konvergerer mod minimum i O(log n).
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])) # 11Antal rotationer og drejepunktets indeks
Når du kan finde minimumselementet, kender du også rotationsantallet: Minimums indeks er præcis det antal positioner, arrayet blev roteret mod højre. I [4,5,6,7,0,1,2] ligger minimum for eksempel på indeks 4, så arrayet blev roteret 4 positioner.
Når du kender drejepunktet, kan du anvende almindelig binær søgning ved at behandle indekser modulo n: real_idx = (mid + pivot) % n. Denne alternative formulering kan gøre det lettere at ræsonnere, når du arbejder med strukturer med cirkulære indekser.
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)) # 4Sæt det hele sammen
Når du møder et problem med et roteret array under et interview, skal du følge dette beslutningstræ. Afgør først, om du skal finde et mål eller finde minimum. Når du skal finde et mål, skal du bruge tilgangen med identifikation af den sorterede halvdel. Når du skal finde minimum, skal du sammenligne mid med hi. Hvis dubletter er mulige, skal du nævne tilfældet O(n) i værste fald og tilføje en fallback, der indsnævrer grænserne.
Øv dig ved at gennemgå din kode med de tre klassiske eksempler: uden rotation, roteret én gang og roteret, så minimum ligger på den sidste position.
Hurtigt tjek
Afprøv din forståelse af begreberne i Data Structures & Algorithms — Coding Interview Prep fra denne lektion.
Opsummering af lektionen
I denne lektion lærte du: et roteret sorteret array altid har mindst én sorteret halvdel, du skal sammenligne arr[lo] med arr[mid] for at identificere den sorterede halvdel, før du beslutter, hvor du skal søge, og når du finder minimum, skal du bruge arr[mid] i forhold til arr[hi] til at finde rotationsdrejepunktet. Derefter ser vi på varianter af binær søgning med nedre og øvre grænse.
Lær Python med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 30
- Lektioner
- 120
Ofte stillede spørgsmål
Er lektionen “Binær søgning i roterede og usorterede arrays” gratis?
Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “Binær søgning i roterede og usorterede arrays”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Binær søgning i roterede og usorterede arrays”?
Løs search-in-rotated-sorted-array og find-minimum-in-rotated-array ved at afgøre, hvilken halvdel der er sorteret i hvert trin. Du øver dig i DSA Interview Prep med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på DSA Interview Prep?
Der kræves ingen tidligere erfaring. DSA Interview Prep på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 2 af 4.
Hvor lang tid tager lektionen “Binær søgning i roterede og usorterede arrays”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne DSA Interview Prep-lektion?
Ja. Alle DSA Interview Prep-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Klassisk binær søgning: venstre, højre, midt
- Binær søgning i roterede og usorterede arrays
- Nedre og øvre grænse
- Binær søgning i svarområdet