Binäärihaku käännetyistä ja järjestämättömistä taulukoista
Ratkaiskaa search-in-rotated-sorted-array- ja find-minimum-in-rotated-array-tehtävät päättämällä jokaisessa vaiheessa, kumpi puolisko on järjestetty.
Binäärihaku käännetyistä ja järjestämättömistä taulukoista on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 2/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mikä on kierrolla siirretty lajiteltu taulukko?
Kierrolla siirretty lajiteltu taulukko on lajiteltu taulukko, joka on katkaistu jostakin pivot-kohdasta ja jonka kaksi osaa on vaihdettu keskenään. Esimerkiksi [4, 5, 6, 7, 0, 1, 2] on lajitellun taulukon [0,1,2,4,5,6,7] indeksissä 4 tehdyn kierron tulos. Tavallinen binäärihaku ei toimi tässä, koska taulukko ei ole enää kokonaisuudessaan lajiteltu.
Keskeinen oivallus on, että vähintään toinen taulukon puoliskoista on aina lajiteltu kierron jälkeen. Binäärihaussa on selvitettävä, kumpi puolisko on lajiteltu, ennen kuin päätetään, miten rajoja siirretään.
# 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 crossingJärjestetyn puoliskon tunnistaminen
Kun mid on laskettu, verratkaa arr[lo]- ja arr[mid]-arvoja. Jos arr[lo] <= arr[mid], vasen puolisko on järjestetty; muuten oikea puolisko on järjestetty. Kun tiedätte, kumpi puolisko on järjestetty, voitte tarkistaa, osuuko kohde kyseiselle järjestetylle alueelle, ja rajata haun sen perusteella.
Tämän päätöspuun avulla voitte hylätä täsmälleen puolet taulukosta jokaisella askeleella, joten O(log n) -aikavaativuus säilyy myös kierretystä taulukosta haettaessa.
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)) # -1Esimerkin läpikäynti
Käykäämme search_rotated([4,5,6,7,0,1,2], 0) läpi vaihe vaiheelta. Aluksi lo=0, hi=6, mid=3, arr[mid]=7. Onko kohde 0 järjestetyssä vasemmassa puoliskossa [4..7]? Ei, joten siirrämme kohdan lo=4. Nyt lo=4, hi=6, mid=5, arr[mid]=1. Vasen puolisko [0,1] on järjestetty (arr[lo]=0 <= arr[mid]=1). Onko 0 välillä [0..1)? Kyllä, joten asetamme hi=4. Nyt lo=4, hi=4, mid=4, arr[4]=0 — alkio löytyi indeksistä 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)Duplikaattien käsittely kierrossa
Kun kierretty taulukko voi sisältää duplikaatteja (esimerkiksi [1,3,1,1,1]), ehto nums[lo] == nums[mid] on tulkinnanvarainen — ette voi päätellä, kumpi puolisko on järjestetty. Turvallinen ratkaisu on kasvattaa lo-arvoa yhdellä (tai pienentää hi-arvoa yhdellä) ja yrittää uudelleen. Tämä heikentää huonoimman tapauksen aikavaativuuden arvoon O(n), mikä kannattaa mainita haastattelijalle.
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)) # TruePienimmän alkion etsiminen kierretystä järjestetystä taulukosta
Aiheeseen liittyvässä tehtävässä etsitään pienin alkio kierretystä järjestetystä taulukosta ilman tiettyä kohdetta. Pienin alkio on aina järjestämättömässä puoliskossa. Toimikaa jokaisella askeleella näin: jos arr[mid] > arr[hi], pienin alkio on oikeassa puoliskossa (lo = mid + 1); muussa tapauksessa se on vasemmassa puoliskossa, johon myös mid kuuluu (hi = mid). Kun lo == hi, olette löytäneet pienimmän alkion.
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)Miksi arr[lo] <= arr[mid] tunnistaa järjestetyn vasemman puoliskon
Ehto arr[lo] <= arr[mid] toimii, koska järjestetyssä (tai kiertämättömässä järjestetyssä) osassa ensimmäinen alkio on aina pienin. Jos arr[lo] <= arr[mid], välillä [lo..mid] ei tapahtunut kiertoa, joten kyseinen puolisko on järjestetty. Yhtäsuuruus kattaa tilanteen, jossa lo == mid (yhden alkion osa on luonnostaan järjestetty).
Vastaavasti, jos arr[lo] > arr[mid], kierron pivotin on sijaittava lo:n ja midin välissä, joten oikea puolisko [mid..hi] on yhtenäinen järjestetty osa.
# 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')Aikavaativuusanalyysi
Kierretystä järjestetystä taulukosta etsiminen binäärihaulla säilyttää ajan O(log n) ja tilan O(1) suhteen, koska puolittamme hakuavaruutta jokaisella iteraatiolla. Ainoa ero tavalliseen binäärihakuun on vakioajassa tehtävä lisätarkistus, jolla selvitetään, kumpi puolisko on järjestetty.
Duplikaattien kanssa huonoin tapaus heikkenee arvoon O(n), koska saatamme kasvattaa lo-arvoa kullakin askeleella vain yhdellä. Mainitkaa tämä vaihtokauppa erikseen — se osoittaa, että huomioitte myös onnistuneen peruspolun ulkopuoliset kulmatapaukset.
LeetCode 33:n läpikäynti
LeetCode 33 'Search in Rotated Sorted Array' on tämän ongelman perusmuoto. Rajoitteet takaavat, ettei duplikaatteja ole ja että taulukko on kierretty täsmälleen kerran. Ratkaisu on aiemmin kirjoittamamme search_rotated-funktio. Haastattelun kannalta keskeistä on ilmoittaa aina duplikaattien puuttumista koskeva oletus, tarkistaa epäyhtälöt konkreettisella raja-arvoesimerkillä ja varmistaa, että palautettu indeksi on oikein sekä löytyneessä että löytymättömässä tapauksessa.
# 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: Pienimmän alkion etsiminen ilman duplikaatteja
LeetCode 153 'Find Minimum in Rotated Sorted Array' pyytää etsimään pienimmän alkion ilman duplikaatteja. Ratkaisussa verrataan arr[mid]- ja arr[hi]-arvoja (ei arr[lo]-arvoa), jotta voidaan määrittää, kummalla puolella pienin alkio on. Jos arr[mid] > arr[hi], pienin alkio on oikealla; muussa tapauksessa se on kohdassa mid tai sen vasemmalla puolella. Näin pienin alkio löytyy O(log n) -ajassa.
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])) # 11Kiertojen määrä ja pivot-indeksi
Kun osaatte löytää pienimmän alkion, tiedätte myös kiertojen määrän: pienimmän alkion indeksi kertoo täsmälleen, kuinka monta paikkaa oikealle taulukkoa kierrettiin. Esimerkiksi taulukossa [4,5,6,7,0,1,2] pienin alkio on indeksissä 4, joten taulukkoa kierrettiin 4 paikkaa.
Pivotin avulla voitte käyttää tavallista binäärihakua käsittelemällä indeksejä modulo n: real_idx = (mid + pivot) % n. Tämä vaihtoehtoinen muotoilu voi helpottaa päättelyä, kun käsittelette ympyräindeksoituja rakenteita.
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)) # 4Kaikki osat yhdessä
Kun kohtaatte haastattelussa kierrettyä taulukkoa koskevan ongelman, noudattakaa tätä päätöspuuta. Määrittäkää ensin, pitääkö etsiä kohdetta vai etsiä pienin alkio. Kun etsitte kohdetta, käyttäkää järjestetyn puoliskon tunnistamiseen perustuvaa lähestymistapaa. Kun etsitte pienintä alkiota, verratkaa mid-arvoa hi-arvoon. Jos duplikaatit ovat mahdollisia, mainitkaa O(n):n huonoin tapaus ja lisätkää varamenettely, jossa rajoja kavennetaan.
Harjoitelkaa jäljittämällä koodin suoritus kolmella klassisella esimerkillä: kiertämätön taulukko, kerran kierretty taulukko ja taulukko, joka on kierretty siten, että pienin alkio on viimeisessä kohdassa.
Pikatarkistus
Testatkaa tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -aiheen ymmärtämistänne.
Oppitunnin kertaus
Tässä oppitunnissa opitte, että kierretystä järjestetystä taulukosta löytyy aina vähintään yksi järjestetty puolisko, että vertaamalla arr[lo]-arvoa arr[mid]-arvoon voidaan tunnistaa järjestetty puolisko ennen kuin päätetään, mistä haetaan ja että pienimmän alkion etsimisessä verrataan arr[mid]- ja arr[hi]-arvoja kierron pivotin paikantamiseksi. Seuraavaksi tarkastelemme alaraja- ja yläraja-binaarihaun muunnelmia.
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Binäärihaku käännetyistä ja järjestämättömistä taulukoista” ilmainen?
Kyllä – oppitunnin ”Binäärihaku käännetyistä ja järjestämättömistä taulukoista” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Binäärihaku käännetyistä ja järjestämättömistä taulukoista”?
Ratkaiskaa search-in-rotated-sorted-array- ja find-minimum-in-rotated-array-tehtävät päättämällä jokaisessa vaiheessa, kumpi puolisko on järjestetty. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 2/4.
Kuinka kauan ”Binäärihaku käännetyistä ja järjestämättömistä taulukoista”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Klassinen binäärihaku: vasen, oikea, keskikohta
- Binäärihaku käännetyistä ja järjestämättömistä taulukoista
- Alaraja ja yläraja
- Vastausavaruuden binäärihaku