Search in Rotated Sorted Array

Q: Apa kompleksitas waktu untuk mencari dalam array terurut yang diputar?

Waktu O(log n) dan ruang tambahan O(1) . Setiap langkah mempertahankan satu setengah dari rentang, jadi 5000 elemen membutuhkan paling banyak 13 langkah. Menemukan titik rotasi terlebih dahulu juga membutuhkan waktu O(log n) , dengan jumlah langkah sekitar dua kali lipat.

Q: Apakah algoritmanya berfungsi saat array berisi nilai duplikat?

Tidak seperti yang tertulis. Saat nums[lo] , nums[mid] , dan nums[hi] sama, tidak ada bagian yang bisa dipastikan terurut. Solusi yang umum adalah memajukan lo satu langkah dalam kasus itu. Cara ini menjaga jawaban tetap benar, tetapi membuat kompleksitas kasus terburuk menjadi O(n) .

Q: Apakah sebaiknya kamu menemukan titik rotasi terlebih dahulu atau mencari dalam satu kali lintasan?

Keduanya berjalan dalam O(log n) . Menemukan nilai minimum terlebih dahulu membagi masalah menjadi dua pencarian biner biasa. Pencarian satu lintasan menyelesaikan tugas dalam satu perulangan dengan langkah yang lebih sedikit, dan inilah versi yang diharapkan sebagian besar pewawancara.

SedangBinary search

+10

Sebuah list berisi bilangan bulat berbeda diurutkan dari yang terkecil ke terbesar, lalu diputar: sejumlah elemen, mungkin nol, diambil dari bagian depan dan dipindahkan ke bagian belakang dengan urutan yang sama. Misalnya, [2, 5, 8, 11, 15, 19, 23] yang diputar sebanyak 4 menjadi [15, 19, 23, 2, 5, 8, 11]. Kamu mendapatkan list yang sudah diputar nums dan bilangan bulat target. Kembalikan indeks target di nums, dihitung dari 0, atau -1 jika tidak ada, dalam waktu O(log n).

Fungsi

search(nums: integer-array, target: integer) → integer

numsinteger-array: list bilangan bulat berbeda yang dirotasi lalu diurutkan
targetinteger: nilai yang dicari
Mengembalikaninteger: indeks target dalam nums, atau -1 jika tidak ditemukan

Batasan

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

Contoh

Input: nums = [15, 19, 23, 2, 5, 8, 11]target = 5
Output: 4
Penjelasan: Nilai tengah pertama, indeks 3, berisi 2, jadi bagian kanan [2, 5, 8, 11] sudah terurut dan berisi 5. Nilai tengah berikutnya, indeks 5, berisi 8; bagian kiri yang sudah terurut, [5, 8], berisi 5, sehingga mengarah ke indeks 4.

Input: nums = [40, 50, 60, 70, 10, 20, 30]target = 65
Output: -1
Penjelasan: 65 seharusnya berada di antara 60 dan 70, tetapi tidak ada elemen yang menyimpannya. Nilai tengah pertama, 70, menempatkan 65 di dalam bagian kiri yang sudah diurutkan [40, 50, 60, 70], lalu rentangnya terus menyusut hingga kosong.

Input: nums = [8, 13, 21, 1, 3, 5]target = 13
Output: 1
Penjelasan: Nilai tengah pertama, indeks 2, berisi 21. Bagian kiri [8, 13, 21] sudah terurut dan 13 berada di antara 8 dan 21, jadi bagian kanan dibuang. Pencarian kemudian menemukan 13 pada indeks 1.

Pertanyaan lanjutan

Jika nums mungkin berisi duplikat, tidak ada algoritma yang dapat menjamin O(log n). Bisakah kamu membuktikannya dengan list berisi angka 1 yang dirotasi dan menyembunyikan satu angka 0?

Petunjuk

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

0 dari 3 dibuka

Solusi

list terurut yang diputar terdiri dari dua rangkaian terurut: [15, 19, 23] lalu [2, 5, 8, 11]. Membandingkan target dengan nilai tengah tidak lagi memberi tahu kamu sisi mana yang memuatnya. Namun, di mana pun kamu membagi list, setidaknya satu bagiannya terurut, dan satu perbandingan memberi tahu kamu apakah target mungkin berada di bagian itu.

Pindai setiap elemen

Intuisi

Periksa setiap indeks dan kembalikan indeks pertama yang nilainya sama dengan target, atau -1 setelah perulangan. Cara ini membaca setiap elemen, jadi benar untuk list apa pun. Cara ini mengabaikan dua bagian yang sudah terurut: 5000 elemen memerlukan hingga 5000 perbandingan, sedangkan pencarian biner hanya memerlukan 13.

Algoritma

Untuk setiap indeks i dari 0 hingga n-1, bandingkan nums[i] dengan target.
Jika keduanya sama, kembalikan i.
Setelah perulangan, kembalikan -1.

def search(nums, target):
    for i, value in enumerate(nums):
        if value == target:
            return i
    return -1

Temukan titik rotasi, lalu lakukan pencarian biner

Intuisi

Perulangan kedua dimulai dari nilai terkecil; sebut indeksnya k. Baik nums[k..n-1] maupun nums[0..k-1] terurut, dan setiap nilai pada perulangan pertama lebih besar daripada setiap nilai pada perulangan kedua. Setelah mengetahui k, bandingkan target dengan nums[k] dan nums[n-1] untuk memilih perulangannya, lalu pencarian biner biasa akan menyelesaikannya.

Untuk menemukan k, bandingkan nilai tengah dengan nums[hi]. Jika nums[mid] > nums[hi], nilai-nilai menurun di suatu tempat setelah mid, jadi nilai minimum berada di sebelah kanannya. Jika tidak, nums[mid..hi] meningkat tanpa penurunan, jadi nilai minimum berada di mid atau sebelumnya. Pada contoh pertama, nilai tengahnya adalah 2, 19, dan 23, sehingga diperoleh k = 3, dan 5 berada di antara nums[3] = 2 dan nums[6] = 11. Dua pencarian biner memerlukan sekitar 2 log2 n langkah.

Algoritma

Tetapkan lo = 0 dan hi = n-1. Selama lo < hi, hitung mid; jika nums[mid] > nums[hi], tetapkan lo = mid + 1, jika tidak, tetapkan hi = mid.
Indeks terakhir k menyimpan nilai terkecil.
Jika nums[k] ≤ target ≤ nums[n-1], lakukan pencarian biner pada indeks k hingga n-1; jika tidak, cari dari 0 hingga k-1.
Kembalikan indeks yang ditemukan, atau -1 jika rentangnya kosong.

def search(nums, target):
    n = len(nums)
    # 1. Find k, the index of the smallest value, where the second run starts.
    lo, hi = 0, n - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1  # the drop is right of mid
        else:
            hi = mid      # mid is in the low run: the minimum is at mid or left of it
    k = lo
    # 2. nums[k..n-1] and nums[0..k-1] are sorted: search the one whose range holds target.
    if nums[k] <= target <= nums[n - 1]:
        lo, hi = k, n - 1
    else:
        lo, hi = 0, k - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Satu pencarian biner pada bagian yang sudah diurutkan

Intuisi

Pertahankan janji pencarian biner: jika target ada di list, indeksnya berada di antara lo dan hi. Nilai hanya turun sekali di seluruh list, jadi paling banyak satu dari dua bagian di sekitar mid berisi titik penurunan, dan bagian lainnya terurut. Jika nums[lo] ≤ nums[mid], bagian kiri terurut; jika tidak, bagian kanan yang terurut.

Untuk bagian yang terurut, pengujian rentang pada kedua ujungnya menunjukkan apakah target mungkin berada di dalamnya, misalnya nums[lo] ≤ target < nums[mid] pada bagian kiri. Jika mungkin, cari di sana; jika tidak, target hanya mungkin berada di bagian lainnya. Setiap langkah membagi rentang menjadi dua: paling banyak 13 langkah untuk 5000 elemen.

Algoritma

Tetapkan lo = 0 dan hi = n-1.
Selama lo ≤ hi, hitung mid dan kembalikan nilainya jika nums[mid] sama dengan target.
Jika nums[lo] ≤ nums[mid], bagian kiri sudah terurut: tetapkan hi = mid - 1 jika nums[lo] ≤ target < nums[mid], jika tidak, tetapkan lo = mid + 1.
Jika tidak, bagian kanan sudah terurut: tetapkan lo = mid + 1 jika nums[mid] < target ≤ nums[hi], jika tidak, tetapkan hi = mid - 1.
Saat perulangan berakhir, kembalikan -1.

def search(nums, target):
    lo, hi = 0, len(nums) - 1  # target, if present, sits in nums[lo..hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:
            # nums[lo..mid] is sorted: target is in it only if it fits its range
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            # nums[mid..hi] is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Jebakan dan kasus tepi

Menulis nums[lo] < nums[mid] alih-alih ≤. Saat tersisa dua elemen, mid sama dengan lo, dan pengujian ketat menganggap [9, 4] sebagai separuh kanan yang terurut: target = 4 menghasilkan -1.
Membandingkan target dengan nums[mid] terlebih dahulu. Pada contoh pertama dengan target = 19, nilai tengah 2 lebih kecil, jadi pencarian bergerak ke kanan dan melewatkan indeks 1.
Menguji hanya satu ujung dari separuh yang terurut. Pada [40, 50, 60, 70, 80, 10, 20] dengan target = 80, hanya memeriksa target ≥ nums[lo] membuat pencarian mengarah ke [40, 50, 60, 70].
Dalam Rust, k - 1 pada usize mengalami underflow saat k = 0, yaitu pada list yang tidak diputar. Gunakan rentang setengah terbuka.
Dalam Lua dan R, mengembalikan posisi berbasis 1. Kurangi 1.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu untuk mencari dalam array terurut yang diputar?

Waktu O(log n) dan ruang tambahan O(1). Setiap langkah mempertahankan satu setengah dari rentang, jadi 5000 elemen membutuhkan paling banyak 13 langkah. Menemukan titik rotasi terlebih dahulu juga membutuhkan waktu O(log n), dengan jumlah langkah sekitar dua kali lipat.

Apakah algoritmanya berfungsi saat array berisi nilai duplikat?

Tidak seperti yang tertulis. Saat nums[lo], nums[mid], dan nums[hi] sama, tidak ada bagian yang bisa dipastikan terurut. Solusi yang umum adalah memajukan lo satu langkah dalam kasus itu. Cara ini menjaga jawaban tetap benar, tetapi membuat kompleksitas kasus terburuk menjadi O(n).

Apakah sebaiknya kamu menemukan titik rotasi terlebih dahulu atau mencari dalam satu kali lintasan?

Keduanya berjalan dalam O(log n). Menemukan nilai minimum terlebih dahulu membagi masalah menjadi dua pencarian biner biasa. Pencarian satu lintasan menyelesaikan tugas dalam satu perulangan dengan langkah yang lebih sedikit, dan inilah versi yang diharapkan sebagian besar pewawancara.

def search(nums, target):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [15, 19, 23, 2, 5, 8, 11]
target = 5

Output yang diharapkan

Search in Rotated Sorted Array

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Pindai setiap elemen

Temukan titik rotasi, lalu lakukan pencarian biner

Satu pencarian biner pada bagian yang sudah diurutkan

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa