DSA Interview Prep · Pelajaran

Carian Binari pada Tatasusunan Diputar dan Tidak Tersusun

Selesaikan search-in-rotated-sorted-array dan find-minimum-in-rotated-array dengan menentukan separuh yang tersusun pada setiap langkah.

Pelajaran 2 daripada 413 langkah

Carian Binari pada Tatasusunan Diputar dan Tidak Tersusun ialah pelajaran DSA Interview Prep percuma di CoddyKit. Ini ialah pelajaran 2 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran DSA Interview Prep, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.

Apakah Tatasusunan Terisih Berputar?

Tatasusunan terisih berputar ialah tatasusunan terisih yang dipotong pada suatu pangsi, kemudian kedua-dua bahagiannya ditukar. Sebagai contoh, [4, 5, 6, 7, 0, 1, 2] ialah tatasusunan terisih [0,1,2,4,5,6,7] yang diputar pada indeks 4. Carian binari standard gagal di sini kerana tatasusunan itu tidak lagi terisih secara keseluruhan.

Wawasan utamanya ialah sekurang-kurangnya satu separuh tatasusunan sentiasa terisih selepas sebarang putaran. Carian binari anda mesti mengenal pasti separuh yang terisih sebelum menentukan sempadan yang hendak dialihkan.

# 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 crossing

Mengenal Pasti Separuh yang Diisih

Selepas mengira mid, bandingkan arr[lo] dengan arr[mid]. Jika arr[lo] <= arr[mid], separuh kiri telah diisih; jika tidak, separuh kanan telah diisih. Setelah mengetahui separuh yang diisih, anda boleh menyemak sama ada sasaran berada dalam julat yang diisih itu dan mengecilkan carian dengan sewajarnya.

Pepohon keputusan ini membolehkan anda membuang tepat separuh daripada tatasusunan pada setiap langkah, sambil mengekalkan kerumitan O(log n) walaupun dalam tatasusunan yang diputar.

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))  # -1

Menjejaki Contoh

Mari kita jejaki search_rotated([4,5,6,7,0,1,2], 0) langkah demi langkah. Pada mulanya lo=0, hi=6, mid=3, arr[mid]=7. Adakah sasaran 0 berada dalam separuh kiri yang diisih [4..7]? Tidak, jadi kita menetapkan lo=4. Kini lo=4, hi=6, mid=5, arr[mid]=1. Separuh kiri [0,1] telah diisih (arr[lo]=0 <= arr[mid]=1). Adakah 0 berada dalam [0..1)? Ya, jadi kita menetapkan hi=4. Kini lo=4, hi=4, mid=4, arr[4]=0 — ditemui pada 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)

Mengendalikan Pendua dalam Putaran

Apabila tatasusunan yang diputar mungkin mengandungi pendua (contohnya, [1,3,1,1,1]), syarat nums[lo] == nums[mid] adalah kabur — anda tidak dapat menentukan separuh mana yang diisih. Penyelesaian selamat ialah menaikkan lo (atau menurunkan hi) sebanyak satu dan cuba lagi. Ini meningkatkan masa kes terburuk kepada O(n), dan anda wajar menyebutnya kepada penemuduga.

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))  # True

Mencari Unsur Minimum dalam Tatasusunan Diisih yang Diputar

Satu masalah berkaitan meminta anda mencari unsur minimum dalam tatasusunan diisih yang diputar tanpa mencari sasaran khusus. Unsur minimum sentiasa berada dalam separuh yang tidak diisih. Pada setiap langkah: jika arr[mid] > arr[hi], unsur minimum berada di separuh kanan (lo = mid + 1); jika tidak, unsur minimum berada di separuh kiri termasuk mid (hi = mid). Apabila lo == hi, anda telah menemui unsur 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)

Mengapa arr[lo] <= arr[mid] Mengesan Bahagian Kiri yang Diisih

Syarat arr[lo] <= arr[mid] berfungsi kerana dalam segmen yang diisih (atau diisih tanpa putaran), unsur pertama sentiasa yang terkecil. Jika arr[lo] <= arr[mid], tiada putaran berlaku dalam [lo..mid], jadi separuh itu telah diisih. Kesamaan tersebut mengendalikan keadaan apabila lo == mid (segmen satu unsur sememangnya telah diisih).

Sebaliknya, jika arr[lo] > arr[mid], pangsi putaran mestilah terletak antara lo dengan mid, yang bermaksud separuh kanan [mid..hi] ialah segmen bersambung yang diisih.

# 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')

Analisis Kerumitan

Carian dalam tatasusunan diisih yang diputar menggunakan carian binari kekal mengambil masa O(log n) dan ruang O(1) kerana kita masih membahagi dua ruang carian pada setiap lelaran. Satu-satunya perbezaan daripada carian binari klasik ialah semakan tambahan yang mengambil masa malar untuk mengenal pasti separuh yang diisih.

Dengan pendua, kes terburuk merosot kepada O(n) kerana kita mungkin hanya menaikkan lo sebanyak satu pada setiap langkah. Nyatakan pertukaran ini dengan jelas — ini menunjukkan bahawa anda memikirkan kes sudut di luar laluan biasa.

Panduan Langkah demi Langkah LeetCode 33

LeetCode 33, 'Cari dalam Tatasusunan Diisih yang Diputar', ialah bentuk piawai masalah ini. Kekangannya menjamin tiada pendua dan tepat satu putaran. Penyelesaiannya ialah fungsi search_rotated yang kita tulis sebelum ini. Perkara utama dalam temu duga: sentiasa nyatakan andaian bahawa tiada pendua, sahkan ketaksamaan anda dengan contoh konkrit pada sempadan, dan pastikan indeks yang dikembalikan adalah betul untuk kedua-dua kes ditemui dan tidak ditemui.

# 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))               # -1

LeetCode 153: Mencari Minimum Tanpa Pendua

LeetCode 153, 'Mencari Unsur Minimum dalam Tatasusunan Diisih yang Diputar', meminta anda mencari unsur minimum tanpa pendua. Pendekatannya ialah membandingkan arr[mid] dengan arr[hi] (bukan arr[lo]) untuk menentukan di sebelah mana unsur minimum berada. Jika arr[mid] > arr[hi], unsur minimum berada di sebelah kanan; jika tidak, unsur minimum berada pada mid atau di sebelah kiri. Proses ini menumpu kepada unsur minimum dalam 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]))       # 11

Bilangan Putaran dan Indeks Pangsi

Setelah anda dapat mencari unsur minimum, anda juga mengetahui bilangan putaran: indeks unsur minimum tepat menunjukkan berapa banyak kedudukan tatasusunan itu diputar ke kanan. Contohnya, dalam [4,5,6,7,0,1,2], unsur minimum berada pada indeks 4, jadi tatasusunan itu diputar sebanyak 4 kedudukan.

Mengetahui pangsi membolehkan anda menggunakan carian binari standard dengan menganggap indeks sebagai modulo n: real_idx = (mid + pivot) % n. Rumusan alternatif ini boleh memudahkan penaakulan apabila bekerja dengan struktur yang mempunyai indeks berbentuk bulatan.

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))  # 4

Menggabungkan Semuanya

Apabila anda menghadapi masalah tatasusunan yang diputar dalam temu duga, ikuti pepohon keputusan ini. Mula-mula, tentukan sama ada anda perlu mencari sasaran atau mencari unsur minimum. Untuk mencari sasaran, gunakan pendekatan mengenal pasti separuh yang diisih. Untuk mencari unsur minimum, bandingkan mid dengan hi. Jika pendua mungkin wujud, nyatakan kes terburuk O(n) dan tambahkan penyelesaian sandaran pengecilan sempadan.

Berlatihlah dengan menjejaki kod anda pada tiga contoh klasik: tiada putaran, diputar sekali, dan diputar sehingga unsur minimum berada pada kedudukan terakhir.

Semakan Pantas

Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.

Jawab dalam pelajaran interaktif

Imbas Kembali Pelajaran

Dalam pelajaran ini anda telah mempelajari: tatasusunan diisih yang diputar sentiasa mempunyai sekurang-kurangnya satu separuh yang diisih, bandingkan arr[lo] dengan arr[mid] untuk mengenal pasti separuh yang diisih sebelum menentukan tempat carian, dan mencari unsur minimum menggunakan arr[mid] berbanding arr[hi] untuk mencari pangsi putaran. Seterusnya, kita akan meneroka varian carian binari batas bawah dan batas atas.

Percuma untuk bermula

Pelajari Python dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus: 30
Pelajaran: 120

Mula belajar secara percuma Lihat kursus penuh

Soalan Lazim

Adakah pelajaran “Carian Binari pada Tatasusunan Diputar dan Tidak Tersusun” percuma?

Ya — sebanyak 3 pelajaran dalam laluan pembelajaran DSA Interview Prep, termasuk “Carian Binari pada Tatasusunan Diputar dan Tidak Tersusun”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Carian Binari pada Tatasusunan Diputar dan Tidak Tersusun”?

Selesaikan search-in-rotated-sorted-array dan find-minimum-in-rotated-array dengan menentukan separuh yang tersusun pada setiap langkah. Anda berlatih DSA Interview Prep menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan DSA Interview Prep?

Tiada pengalaman terdahulu diperlukan. Pembelajaran DSA Interview Prep di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 2 daripada 4.

Berapa lamakah pelajaran “Carian Binari pada Tatasusunan Diputar dan Tidak Tersusun” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran DSA Interview Prep ini?

Ya. Setiap pelajaran DSA Interview Prep menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

Carian Binari Klasik: Kiri, Kanan, Tengah
Carian Binari pada Tatasusunan Diputar dan Tidak Tersusun
Had Bawah dan Had Atas
Carian Binari Ruang Jawapan

← Kembali ke DSA Interview Prep