Find Minimum in Rotated Sorted Array

Q: Apa kompleksitas waktu untuk menemukan nilai minimum dalam array terurut yang diputar?

Waktu O(log n) dan ruang ekstra O(1) dengan pencarian biner, paling banyak 13 perbandingan untuk 5000 elemen. Penelusuran hingga titik penurunan membutuhkan O(n) : penelusuran ini membaca setiap elemen saat nilai minimum berada di akhir.

Q: Mengapa membandingkan nums[mid] dengan nums[hi], bukan dengan nums[lo]?

nums[hi] selalu memastikan di sisi mana nilai minimum berada. Dengan nums[lo] , hasil nums[mid] > nums[lo] cocok untuk rentang yang tidak diputar, dengan nilai minimum di nums[lo] , maupun rentang yang diputar, dengan nilai minimum berada di sebelah kanan mid .

Q: Bagaimana cara mengetahui berapa kali sebuah array terurut diputar?

Jalankan pencarian biner yang sama dan ambil lo , indeks nilai minimum. Jika rotasi memindahkan elemen terakhir ke depan, indeks itu adalah jumlahnya. Jika rotasi memindahkan elemen pertama ke belakang, seperti di sini, jumlahnya adalah (n - lo) mod n : 7 dikurangi 4 menghasilkan 3 pada contoh pertama.

Q: Apakah binary search berfungsi saat array memiliki elemen duplikat?

Tidak tetap sama. Dalam [2, 2, 2, 0, 2] , nums[mid] dapat sama dengan nums[hi] , sehingga tidak menyingkirkan sisi mana pun. Menetapkan hi = hi - 1 setelah itu aman, karena salinan nums[hi] tetap berada dalam rentang, tetapi kasus terburuknya menjadi O(n) .

SedangBinary search

+10

Sebuah list bilangan bulat berbeda diurutkan secara menaik, lalu diputar: sejumlah elemen, mungkin nol, diambil dari bagian depan dan dipindahkan ke bagian belakang dengan urutan yang sama. Sebagai contoh, [2, 5, 9, 11, 13, 15, 17] yang diputar sebanyak 3 menjadi [11, 13, 15, 17, 2, 5, 9]. Kamu mendapatkan list yang sudah diputar nums. Kembalikan nilai terkecilnya dalam waktu O(log n).

Fungsi

findMin(nums: integer-array) → integer

numsinteger-array: list bilangan bulat berbeda yang terurut dan telah diputar
Mengembalikaninteger: nilai terkecil di nums

Batasan

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
Semua nilai dalam nums berbeda.
nums adalah list dengan nilai yang meningkat, diputar sebanyak nilai k dengan 0 ≤ k < nums.length; k = 0 membuatnya tetap tidak diputar.

Contoh

Input: nums = [11, 13, 15, 17, 2, 5, 9]
Output: 2
Penjelasan: Nilainya naik hingga 17 dan turun hingga 2. Karena 17 > 9, nilai minimum berada di sebelah kanan indeks 3; lalu 5 ≤ 9 dan 2 ≤ 5 menarik hi kembali ke indeks 4, yang berisi 2.

Input: nums = [4, 7, 10, 12]
Output: 4
Penjelasan: list ini diputar sebanyak 0, jadi urutannya masih terurut dan nilai minimumnya adalah nilai pertama. Setiap nilai tengah kurang dari atau sama dengan nilai terakhir, jadi hi terus bergerak ke kiri hingga mencapai indeks 0, yang berisi 4.

Input: nums = [30, -6, 0, 8, 19]
Output: -6
Penjelasan: Rotasi sebanyak 4 menempatkan nilai terbesar, 30, di urutan pertama dan nilai minimum, -6, pada indeks 1. Pencarian menyempit ke indeks 0 dan 1, melihat bahwa 30 > -6, lalu memindahkan lo ke 1.

Pertanyaan lanjutan

Bisakah kamu mengembalikan nilai terkecil ke-k dari nums dalam waktu O(log n), tanpa mengurutkannya?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

list terurut yang diputar terdiri dari dua urutan menaik, dan nilai minimum memulai urutan kedua, tepat setelah satu-satunya tempat nilai menurun. Dengan membandingkan nilai tengah dengan nilai terakhir dalam rentang, kamu bisa mengetahui di sisi mana dari penurunan itu nilai tengah berada, sehingga pencarian biner dapat menemukannya dalam O(log n).

Berjalanlah sampai nilainya berkurang

Intuisi

Rotasi membuat kedua bagian tetap terurut dan menciptakan satu tempat dengan nilai yang lebih kecil daripada nilai sebelumnya: nilai terbesar diikuti nilai terkecil. Telusuri dari kiri ke kanan dan kembalikan nilai pertama yang memenuhi kondisi tersebut. Jika tidak ada, berarti list tidak dirotasi dan nilai minimumnya adalah nums[0].

Penurunan bisa terjadi di mana saja. Jika rotasi memindahkan satu elemen, seperti pada [2, 3, 4, 5, 6, 7, 8, 1], penelusuran membaca seluruh list: 5000 perbandingan untuk 5000 elemen, sedangkan pencarian biner hanya membutuhkan 13.

Algoritma

Untuk setiap indeks i dari 1 hingga n-1, bandingkan nums[i] dengan nums[i-1].
Jika nums[i] < nums[i-1], kembalikan nums[i]: bagian kedua dimulai di sana.
Jika perulangan selesai, list tidak dirotasi: kembalikan nums[0].

def findMin(nums):
    for i in range(1, len(nums)):
        if nums[i] < nums[i - 1]:
            return nums[i]  # the only drop: the second run starts here
    return nums[0]  # no drop: the list was not rotated

Pencarian biner terhadap nilai terakhir

Intuisi

Pertahankan satu janji: nilai minimum berada di antara lo dan hi, termasuk keduanya. Bandingkan nilai tengah dengan nums[hi], nilai terakhir dalam rentang tersebut.

Jika nums[mid] > nums[hi], nilai-nilainya menurun di suatu titik antara mid dan hi, dan nilai minimum berada tepat setelah penurunan itu, jadi tetapkan lo = mid + 1. Jika tidak, nums[mid] < nums[hi], karena semua nilainya berbeda, sehingga nums[mid..hi] meningkat tanpa ada penurunan. Nilai minimum adalah nums[mid] atau berada sebelumnya: tetapkan hi = mid, agar mid tetap berada dalam rentang. Kedua langkah mempertahankan janji dan memperkecil rentang, jadi saat lo bertemu hi, satu nilai yang tersisa adalah nilai minimum.

Setiap langkah membagi dua rentang: paling banyak 13 langkah untuk 5000 elemen, dengan dua indeks sebagai memori tambahan.

Algoritma

Tetapkan lo = 0 dan hi = n-1.
Selama lo < hi, hitung mid = lo + (hi - lo) / 2.
Jika nums[mid] > nums[hi], tetapkan lo = mid + 1.
Jika tidak, tetapkan hi = mid.
Saat perulangan berakhir, kembalikan nums[lo].

def findMin(nums):
    lo, hi = 0, len(nums) - 1  # the minimum sits in nums[lo..hi]
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1  # the values drop after mid, so the minimum is right of it
        else:
            hi = mid      # nums[mid..hi] climbs: the minimum is at mid or left of it
    return nums[lo]

Jebakan dan kasus tepi

Menulis hi = mid - 1 di cabang kedua. Dalam [3, 1, 2], nilai tengah 1 tidak lebih besar dari 2, jadi hi turun menjadi 0 dan fungsi mengembalikan 3.
Melakukan perulangan dengan lo ≤ hi. Setelah lo sama dengan hi, hi = mid tidak mengubah apa pun dan perulangan tidak pernah berakhir.
Membandingkan dengan nums[lo], bukan nums[hi]. Dalam [1, 2, 3, 4, 5] yang tidak dirotasi, nilai tengah 3 lebih besar dari nums[0] = 1, jadi pencarian bergerak ke kanan dan mengembalikan 4.
Tidak memberikan fallback untuk penelusuran pada list yang tidak dirotasi. Dalam [4, 7, 10, 12], tidak ada nilai yang turun, jadi kembalikan nums[0].

Pertanyaan yang sering diajukan4

Apa kompleksitas waktu untuk menemukan nilai minimum dalam array terurut yang diputar?

Waktu O(log n) dan ruang ekstra O(1) dengan pencarian biner, paling banyak 13 perbandingan untuk 5000 elemen. Penelusuran hingga titik penurunan membutuhkan O(n): penelusuran ini membaca setiap elemen saat nilai minimum berada di akhir.

Mengapa membandingkan nums[mid] dengan nums[hi], bukan dengan nums[lo]?

nums[hi] selalu memastikan di sisi mana nilai minimum berada. Dengan nums[lo], hasil nums[mid] > nums[lo] cocok untuk rentang yang tidak diputar, dengan nilai minimum di nums[lo], maupun rentang yang diputar, dengan nilai minimum berada di sebelah kanan mid.

Bagaimana cara mengetahui berapa kali sebuah array terurut diputar?

Jalankan pencarian biner yang sama dan ambil lo, indeks nilai minimum. Jika rotasi memindahkan elemen terakhir ke depan, indeks itu adalah jumlahnya. Jika rotasi memindahkan elemen pertama ke belakang, seperti di sini, jumlahnya adalah (n - lo) mod n: 7 dikurangi 4 menghasilkan 3 pada contoh pertama.

Apakah binary search berfungsi saat array memiliki elemen duplikat?

Tidak tetap sama. Dalam [2, 2, 2, 0, 2], nums[mid] dapat sama dengan nums[hi], sehingga tidak menyingkirkan sisi mana pun. Menetapkan hi = hi - 1 setelah itu aman, karena salinan nums[hi] tetap berada dalam rentang, tetapi kasus terburuknya menjadi O(n).

def findMin(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [11, 13, 15, 17, 2, 5, 9]

Output yang diharapkan