Search in Rotated Sorted Array

Q: Döndürülmüş sıralı bir dizide arama yapmanın zaman karmaşıklığı nedir?

O(log n) zaman ve O(1) ek alan. Her adım aralığın yarısını korur, bu nedenle 5000 öğe en fazla 13 adım gerektirir. Önce döndürme noktasını bulmak da O(log n) zaman alır ve yaklaşık iki katı kadar adım gerektirir.

Q: Algoritma, dizi yinelenen öğeler içerdiğinde çalışır mı?

Yazıldığı şekliyle olmaz. nums[lo] , nums[mid] ve nums[hi] eşit olduğunda, iki yarımdan hiçbirinin sıralı olduğu kanıtlanamaz. Bu durumda yaygın çözüm lo değerini bir artırır; bu, yanıtın doğruluğunu korur ancak en kötü durum karmaşıklığını O(n) yapar.

Q: Dönme noktasını önce mi bulmalısın, yoksa tek geçişte mi aramalısın?

İkisi de O(log n) süresinde çalışır. Önce minimumu bulmak, problemi iki basit ikili aramaya böler. Tek geçişli arama işi daha az adımla tek bir döngüde yapar ve çoğu görüşmecinin beklediği sürüm budur.

Ortaİkili arama

+10

Birbirinden farklı tam sayılardan oluşan bir liste artan sırada sıralandı ve ardından döndürüldü: muhtemelen sıfır olmak üzere belirli sayıda eleman baştan alınıp aynı sırayla sona taşındı. Örneğin, [2, 5, 8, 11, 15, 19, 23] 4 konum döndürüldüğünde [15, 19, 23, 2, 5, 8, 11] olur. Döndürülmüş nums listesini ve bir target tam sayısını alıyorsun. target değerinin nums içindeki indeksini 0'dan başlayarak sayıp döndür; listede yoksa -1 döndür. Bunu O(log n) zamanda yap.

Fonksiyon

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

numsinteger-array: döndürülmüş sıralı farklı tam sayı listesi
targetinteger: aranacak değer
Döndürürinteger: nums içinde target'ın indeksi veya yoksa -1

Kısıtlar

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i], target ≤ 10⁴
<|?
nums, 0 ≤ k < nums.length koşulunu sağlayan bir k kadar döndürülmüş artan bir listedir; k = 0 listeyi döndürülmemiş hâlde bırakır.

Örnekler

Girdi: nums = [15, 19, 23, 2, 5, 8, 11]target = 5
Çıktı: 4
Açıklama: İlk orta eleman, indeks 3, 2 değerini tutar; bu nedenle sağ yarı [2, 5, 8, 11] sıralıdır ve 5 değerini tutar. Sonraki orta eleman, indeks 5, 8 değerini tutar; sıralı sol bölüm [5, 8] 5 değerini tutar ve bu da indeks 4'e götürür.

Girdi: nums = [40, 50, 60, 70, 10, 20, 30]target = 65
Çıktı: -1
Açıklama: 65, 60 ile 70 arasına ait olur ve onu hiçbir öğe içermez. İlk orta değer olan 70, 65'i sıralanmış sol kısım [40, 50, 60, 70] içine yerleştirir ve aralık boşalana kadar orada daralır.

Girdi: nums = [8, 13, 21, 1, 3, 5]target = 13
Çıktı: 1
Açıklama: İlk orta eleman, 2. indeks, 21 değerini tutar. Sol kısım [8, 13, 21] sıralıdır ve 13, 8 ile 21 arasındadır; bu nedenle sağ kısım elenir. Arama daha sonra 13'ü 1. indekste bulur.

Ek soru

Eğer nums yinelenen değerler içerebiliyorsa, hiçbir algoritma O(log n) garantisi veremez. Tek bir 0'ı gizleyen, döndürülmüş bir 1'ler listesiyle bunu kanıtlayabilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Döndürülmüş sıralı bir liste, iki sıralı parçadan oluşur: [15, 19, 23] ve ardından [2, 5, 8, 11]. target değerini ortadaki değerle karşılaştırmak, artık hangi tarafta bulunduğunu söylemez. Ancak listeyi nereden bölersen böl, en az bir yarısı sıralıdır ve tek bir karşılaştırma, target değerinin o yarıda olup olamayacağını söyler.

Her öğeyi tara

Sezgi

Her dizini kontrol et ve değeri target değerine eşit olan ilk dizini döndür; döngüden sonra -1 döndür. Her öğeyi okuduğu için her liste için doğrudur. Sıralanmış iki parçayı göz ardı eder: 5000 öğe en fazla 5000 karşılaştırmaya mal olurken ikili arama 13 karşılaştırma gerektirir.

Algoritma

0'dan n-1'e kadar her i indeksi için nums[i] ile target'ı karşılaştır.
Eşitlerse i değerini döndür.
Döngüden sonra -1 değerini döndür.

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

Dönme noktasını bul, ardından ikili arama yap

Sezgi

İkinci parça en küçük değerden başlar; bu değerin indeksine k diyelim. Hem nums[k..n-1] hem de nums[0..k-1] sıralıdır ve ilk parçadaki her değer, ikinci parçadaki her değerden büyüktür. k değerini bulduktan sonra target değerini nums[k] ve nums[n-1] ile karşılaştırarak hangi parçanın kullanılacağını seçebilir, ardından standart ikili aramayı uygulayabilirsin.

k değerini bulmak için ortadaki değeri nums[hi] ile karşılaştır. nums[mid] > nums[hi] ise değerler mid konumundan sonra bir yerde düşer; dolayısıyla minimum sağındadır. Aksi takdirde nums[mid..hi] aralığı düşüş olmadan yükselir; dolayısıyla minimum mid konumunda ya da ondan öncedir. İlk örnekte orta değerler 2, 19 ve 23'tür; bu da k = 3 sonucunu verir ve 5, nums[3] = 2 ile nums[6] = 11 arasındadır. İki ikili arama yaklaşık 2 log2 n adım sürer.

Algoritma

lo = 0 ve hi = n-1 olarak ayarla. lo < hi olduğu sürece mid değerini hesapla; nums[mid] > nums[hi] ise lo = mid + 1 olarak ayarla, aksi hâlde hi = mid olarak ayarla.
Son indeks k, en küçük değeri tutar.
nums[k] ≤ target ≤ nums[n-1] ise k ile n-1 arasındaki indekslerde ikili arama yap; aksi hâlde 0 ile k-1 arasında ara.
Bulunan indeksi döndür veya aralık boşalırsa -1 döndür.

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

Sıralanmış yarıda bir ikili arama

Sezgi

İkili arama ilkesini koruyun: target listede bulunuyorsa, indeksi lo ile hi arasındadır. Değerler tüm listede yalnızca bir kez düşer; bu nedenle mid etrafındaki iki yarıdan en fazla biri düşüşü içerir, diğeri ise sıralıdır. nums[lo] ≤ nums[mid] ise sol yarı sıralıdır; değilse sağ yarı sıralıdır.

Sıralı yarı için, uçlarındaki iki değer üzerinde yapılan bir aralık testi target değerinin bu aralıkta olup olamayacağını gösterir; örneğin sol yarıda nums[lo] ≤ target < nums[mid]. Olabiliyorsa orada arama yapın; olamıyorsa target yalnızca diğer yarıda olabilir. Her adımda aralık yarıya iner: 5000 öğe için en fazla 13 adım gerekir.

Algoritma

lo = 0 ve hi = n-1 olarak ayarla.
lo ≤ hi olduğu sürece mid değerini hesapla ve nums[mid], target değerine eşitse mid değerini döndür.
nums[lo] ≤ nums[mid] ise sol yarı sıralıdır: nums[lo] ≤ target < nums[mid] olduğunda hi = mid - 1, aksi hâlde lo = mid + 1 olarak ayarla.
Aksi hâlde sağ yarı sıralıdır: nums[mid] < target ≤ nums[hi] olduğunda lo = mid + 1, aksi hâlde hi = mid - 1 olarak ayarla.
Döngü sona erdiğinde -1 değerini döndür.

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

Tuzaklar ve uç durumlar

nums[lo] < nums[mid] yerine ≤ yazmak. İki öğe kaldığında mid, lo'ya eşittir ve katı koşul [9, 4] dizisini sıralı bir sağ yarı olarak kabul eder: target = 4, -1 döndürür.
Önce target ile nums[mid]'i karşılaştırmak. target = 19 olan ilk örnekte ortadaki 2 daha küçüktür; bu nedenle arama sağa ilerler ve 1. indeksi kaçırır.
Sıralı yarının yalnızca bir ucunu sınamak. [40, 50, 60, 70, 80, 10, 20] içinde target = 80 olduğunda, yalnızca target ≥ nums[lo] koşulu aramayı [40, 50, 60, 70] aralığına yönlendirir.
Rust'ta, döndürülmemiş liste olan k = 0 durumunda, usize türündeki k - 1 taşmaya yol açar. Yarı açık aralıklar kullanın.
Lua ve R'de 1 tabanlı konumu döndürmek. 1 çıkarın.

Sıkça sorulan sorular3

Döndürülmüş sıralı bir dizide arama yapmanın zaman karmaşıklığı nedir?

O(log n) zaman ve O(1) ek alan. Her adım aralığın yarısını korur, bu nedenle 5000 öğe en fazla 13 adım gerektirir. Önce döndürme noktasını bulmak da O(log n) zaman alır ve yaklaşık iki katı kadar adım gerektirir.

Algoritma, dizi yinelenen öğeler içerdiğinde çalışır mı?

Yazıldığı şekliyle olmaz. nums[lo], nums[mid] ve nums[hi] eşit olduğunda, iki yarımdan hiçbirinin sıralı olduğu kanıtlanamaz. Bu durumda yaygın çözüm lo değerini bir artırır; bu, yanıtın doğruluğunu korur ancak en kötü durum karmaşıklığını O(n) yapar.

Dönme noktasını önce mi bulmalısın, yoksa tek geçişte mi aramalısın?

İkisi de O(log n) süresinde çalışır. Önce minimumu bulmak, problemi iki basit ikili aramaya böler. Tek geçişli arama işi daha az adımla tek bir döngüde yapar ve çoğu görüşmecinin beklediği sürüm budur.

def search(nums, target):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

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

Beklenen Çıktı

Search in Rotated Sorted Array

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Her öğeyi tara

Dönme noktasını bul, ardından ikili arama yap

Sıralanmış yarıda bir ikili arama

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler