Pencarian Biner pada Array Terputar dan Tak Terurut
Selesaikan search-in-rotated-sorted-array dan find-minimum-in-rotated-array dengan menentukan bagian mana yang terurut pada setiap langkah.
Pencarian Biner pada Array Terputar dan Tak Terurut adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa Itu Larik Terurut yang Diputar?
Larik terurut yang diputar adalah larik terurut yang dipotong pada suatu titik pemisah, lalu kedua bagiannya ditukar. Sebagai contoh, [4, 5, 6, 7, 0, 1, 2] adalah larik terurut [0,1,2,4,5,6,7] yang diputar mulai indeks 4. Pencarian biner standar gagal di sini karena larik tidak lagi terurut secara global.
Wawasan utamanya adalah bahwa setidaknya satu paruh larik selalu terurut setelah rotasi apa pun. Pencarian biner Anda harus mengidentifikasi paruh mana yang terurut sebelum menentukan ke mana batas harus digeser.
# 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 crossingMengidentifikasi Paruh yang Terurut
Setelah menghitung mid, bandingkan arr[lo] dengan arr[mid]. Jika arr[lo] <= arr[mid], paruh kiri terurut; jika tidak, paruh kanan terurut. Setelah mengetahui paruh mana yang terurut, Anda dapat memeriksa apakah sasaran berada dalam rentang terurut tersebut dan mempersempit pencarian sebagaimana mestinya.
Pohon keputusan ini memungkinkan Anda membuang tepat separuh larik pada setiap langkah, sehingga kompleksitas O(log n) tetap terjaga bahkan pada larik 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)) # -1Menelusuri Contoh
Mari kita telusuri search_rotated([4,5,6,7,0,1,2], 0) langkah demi langkah. Pada awalnya lo=0, hi=6, mid=3, arr[mid]=7. Apakah sasaran 0 berada di paruh kiri yang terurut [4..7]? Tidak, jadi kita memindahkan lo=4. Sekarang lo=4, hi=6, mid=5, arr[mid]=1. Paruh kiri [0,1] terurut (arr[lo]=0 <= arr[mid]=1). Apakah 0 berada dalam [0..1)? Ya, jadi hi=4. Sekarang lo=4, hi=4, mid=4, arr[4]=0 — ditemukan 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)Menangani Duplikat dalam Rotasi
Jika larik yang diputar mungkin berisi duplikat (misalnya, [1,3,1,1,1]), kondisi nums[lo] == nums[mid] menjadi ambigu — Anda tidak dapat mengetahui paruh mana yang terurut. Solusi yang aman adalah menambah lo (atau mengurangi hi) sebesar satu, lalu mencoba lagi. Dalam kasus terburuk, waktu eksekusi memburuk menjadi O(n), dan Anda sebaiknya menyebutkan hal ini kepada pewawancara.
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)) # TrueMenemukan Nilai Minimum pada Larik Terurut yang Diputar
Masalah terkait meminta Anda menemukan elemen minimum dalam larik terurut yang diputar tanpa mencari sasaran tertentu. Nilai minimum selalu berada di paruh yang tidak terurut. Pada setiap langkah: jika arr[mid] > arr[hi], nilai minimum berada di paruh kanan (lo = mid + 1); jika tidak, nilai minimum berada di paruh kiri termasuk mid (hi = mid). Saat lo == hi, Anda telah menemukan nilai 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] Mendeteksi Paruh Kiri yang Terurut
Kondisi arr[lo] <= arr[mid] berfungsi karena dalam segmen yang terurut (atau terurut tanpa rotasi), elemen pertama selalu merupakan yang terkecil. Jika arr[lo] <= arr[mid], tidak terjadi rotasi dalam [lo..mid], sehingga paruh tersebut terurut. Kesetaraan tersebut menangani kasus ketika lo == mid (segmen yang terdiri dari satu elemen secara otomatis terurut).
Sebaliknya, jika arr[lo] > arr[mid], pivot rotasi pasti berada di antara lo dan mid, yang berarti paruh kanan [mid..hi] merupakan segmen terurut yang berkesinambungan.
# 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 Kompleksitas
Pencarian pada larik terurut yang diputar dengan pencarian biner tetap memiliki waktu O(log n) dan ruang O(1) karena kita tetap membagi dua ruang pencarian pada setiap iterasi. Satu-satunya perbedaan dari pencarian biner klasik adalah pemeriksaan tambahan berwaktu konstan untuk mengidentifikasi paruh yang terurut.
Dengan duplikat, kasus terburuk memburuk menjadi O(n) karena kita mungkin hanya menambah lo sebesar satu pada setiap langkah. Sebutkan pertukaran ini secara eksplisit — hal tersebut menunjukkan bahwa Anda memikirkan kasus batas di luar jalur normal.
Penelusuran LeetCode 33
LeetCode 33 'Mencari dalam Larik Terurut yang Diputar' adalah bentuk standar dari masalah ini. Batasan soalnya menjamin tidak ada duplikat dan tepat satu rotasi. Solusinya adalah fungsi search_rotated yang telah kita tulis sebelumnya. Poin penting dalam wawancara: selalu nyatakan asumsi bahwa tidak ada duplikat, verifikasi pertidaksamaan Anda dengan contoh konkret di batas, dan pastikan indeks yang dikembalikan benar untuk kasus sasaran ditemukan maupun tidak ditemukan.
# 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: Menemukan Minimum Tanpa Duplikat
LeetCode 153 'Menemukan Minimum dalam Larik Terurut yang Diputar' meminta Anda menemukan nilai minimum tanpa duplikat. Pendekatannya adalah membandingkan arr[mid] dengan arr[hi] (bukan arr[lo]) untuk menentukan di sisi mana nilai minimum berada. Jika arr[mid] > arr[hi], nilai minimum berada di sebelah kanan; jika tidak, nilai minimum berada di mid atau di sebelah kiri. Proses ini mengarah ke nilai 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])) # 11Jumlah Rotasi dan Indeks Pivot
Setelah Anda dapat menemukan elemen minimum, Anda juga mengetahui jumlah rotasi: indeks elemen minimum tepat sama dengan jumlah posisi pergeseran larik ke kanan. Contohnya, dalam [4,5,6,7,0,1,2], nilai minimum berada pada indeks 4, jadi larik tersebut diputar sebanyak 4 posisi.
Dengan mengetahui pivot, Anda dapat menerapkan pencarian biner standar dengan memperlakukan indeks secara modulo n: real_idx = (mid + pivot) % n. Rumusan alternatif ini dapat menyederhanakan penalaran saat bekerja dengan struktur yang indeksnya melingkar.
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)) # 4Menyatukan Semuanya
Saat menemukan masalah tentang larik yang diputar dalam wawancara, ikuti pohon keputusan ini. Pertama, tentukan apakah Anda perlu menemukan sasaran atau menemukan nilai minimum. Untuk menemukan sasaran, gunakan pendekatan identifikasi paruh terurut. Untuk menemukan nilai minimum, bandingkan mid dengan hi. Jika duplikat mungkin ada, sebutkan kasus terburuk O(n) dan tambahkan mekanisme cadangan berupa penyempitan batas.
Berlatihlah dengan menelusuri kode Anda pada tiga contoh klasik: tanpa rotasi, diputar satu kali, dan diputar sehingga nilai minimum berada di posisi terakhir.
Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda telah mempelajari: larik terurut yang diputar selalu memiliki setidaknya satu paruh yang terurut, bandingkan arr[lo] dengan arr[mid] untuk mengidentifikasi paruh yang terurut sebelum menentukan lokasi pencarian, dan pencarian nilai minimum menggunakan arr[mid] dibandingkan dengan arr[hi] untuk menemukan pivot rotasi. Selanjutnya kita akan membahas variasi pencarian biner batas bawah dan batas atas.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Pencarian Biner pada Array Terputar dan Tak Terurut” gratis?
Ya — teks lengkap “Pencarian Biner pada Array Terputar dan Tak Terurut” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Pencarian Biner pada Array Terputar dan Tak Terurut”?
Selesaikan search-in-rotated-sorted-array dan find-minimum-in-rotated-array dengan menentukan bagian mana yang terurut pada setiap langkah. Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.
Berapa lama pelajaran “Pencarian Biner pada Array Terputar dan Tak Terurut” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Pencarian Biner Klasik: Kiri, Kanan, Tengah
- Pencarian Biner pada Array Terputar dan Tak Terurut
- Batas Bawah dan Batas Atas
- Pencarian Biner pada Ruang Jawaban