Search in Rotated Sorted Array
Birbirinden farklı tam sayılardan oluşan bir liste artan sırada sıralandı ve ardından döndürüldü: sıfır veya daha fazla sayıda öğe baştan alınıp aynı sırayla sona taşındı. Örneğin, [2, 5, 8, 11, 15, 19, 23] listesi 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ırsınız. target değerinin nums içindeki indeksini 0'dan başlayarak döndürün; listede yoksa -1 döndürün. Bunu O(log n) zamanda yapın.
Fonksiyon
- numsinteger-array
- döndürülmüş sıralı farklı tam sayılar listesi
- targetinteger
- aranacak değer
- Döndürürinteger
- nums içindeki target öğesinin indeksi veya bulunmuyorsa -1
Kısıtlar
1 ≤ nums.length ≤ 5000-104 ≤ nums[i], target ≤ 104- Tüm
numsdeğerleri birbirinden farklıdır. nums,0 ≤ k < nums.lengtholacak şekilde birkdeğeri kadar döndürülmüş artan bir listedir;k = 0ise döndürülmeden kalır.
Örnekler
- Girdi
- nums = [15, 19, 23, 2, 5, 8, 11]target = 5
- Çıktı
- 4
- Açıklama
- 5, 4. indekste yer alır. İlk orta eleman olan 3. indekste 2 bulunur; dolayısıyla sağ yarı
[2, 5, 8, 11]sıralıdır ve 5, 2 ile 11 arasındadır. Bir sonraki orta eleman olan 5. indekste 8 bulunur; sıralı sol kısım[5, 8]içinde 5 yer alır ve bu da 4. indekse 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 olurdu ve hiçbir öğe onu içermez. İlk orta değer olan, 3. indeksteki 70, 65'i sıralı sol kısım olan
[40, 50, 60, 70]içine yerleştirir. Aralık, bu bölümün içinde boşalana kadar daralır; bu nedenle işlev-1döndürü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ında yer alır; bu nedenle sağ kısmın tamamı elenir. Arama daha sonra 13'ü 1. indekste bulur.
Gönderirken +23 gizli test
Ek soru
nums yinelenen değerler içerebiliyorsa hiçbir algoritma O(log n) garantisi veremez. Bunu kanıtlayabilir misin? İçinde tek bir 0 gizlenmiş 1'lerden oluşan döndürülmüş bir liste oluştur; 0'ı arayan herhangi bir aramanın her öğeyi okuması gereksin.
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Herhangi bir orta indeks seçin ve onun iki yanındaki iki yarıya bakın. Döndürme, değerlerin en büyükten en küçüğe düştüğü bir yer oluşturdu. Bu düşüş her iki yarıda da olabilir mi?
En az bir yarı her zaman sıralıdır ve
nums[lo]ilenums[mid]karşılaştırması hangisinin sıralı olduğunu gösterir. Sıralı bir yarı için,targetdeğerinin ilk ve son değer arasında olup olmadığını tek adımda kontrol edebilirsiniz.lovehideğerlerini,targetdeğerini hâlâ içerebilecek bölümün sınırlarında tut. Her adımda, sıralı yarının değer aralığıtargetdeğerini içeriyorsa o yarıyı tut; aksi hâlde diğer yarıyı tut.targetdeğerini bulduğunda veya aralık boş olduğunda dur.
Çözüm
Döndürülmüş sıralı bir liste, art arda gelen iki sıralı diziden oluşur: [15, 19, 23] ve ardından [2, 5, 8, 11]. Standart ikili arama bu listede başarısız olur; çünkü target ile ortadaki değeri karşılaştırmak, target'ın hangi tarafta olduğunu artık göstermez. Çözüm tek bir gerçeğe dayanır: listeyi nereden bölersen böl, iki yarıdan en az biri tamamen sıralıdır ve sıralı bir yarı için tek bir karşılaştırmayla target'ın içinde olup olamayacağını anlayabilirsin.
Her öğeyi tara
Sezgi
Her indeksi sırayla kontrol et ve değeri target'a eşit olan ilk indeksin değerini döndür. Döngü eşleşme olmadan biterse -1 döndür. Değerler birbirinden farklıdır, dolayısıyla ilk eşleşme tektir ve tarama, liste döndürülmüş olsun ya da olmasın, her liste için doğrudur.
Bu yaklaşım, problemin sana söylediği her şeyi göz ardı eder. Liste, sıralı iki parçadan oluşur; buna rağmen tarama 5000 öğenin tümünü okuyabilirken ikili arama yaklaşık 13 karşılaştırma gerektirir. Girdi büyüdükçe fark da artar: bir milyon öğe, yaklaşık 20 karşılaştırmaya karşılık bir milyon karşılaştırma gerektirir. Görev O(log n) istiyor; bu nedenle bu, iyileştirmen gereken temel yaklaşımdır, yanıt değil.
Algoritma
- 0'dan
n-1'e kadar heriindeksi içinnums[i]iletarget'ı karşılaştır. - Eşitlerse
i'yi döndür. - Döngüden sonra
-1'i döndür.
def search(nums, target):
for i, value in enumerate(nums):
if value == target:
return i
return -1Dönme noktasını bul, ardından ikili arama yap
Sezgi
Döndürülmüş liste, iki sıralı parçadan oluşur ve ikinci parça en küçük değerden başlar. Bu parçanın indeksine k diyelim. k değerini öğrendikten sonra problem, basit bir ikili aramaya dönüşür: nums[k..n-1] sıralıdır ve nums[k] ile nums[n-1] arasındaki değerleri içerir; nums[0..k-1] de sıralıdır ve daha büyük olan tüm değerleri içerir. target değerini nums[k] ve nums[n-1] ile karşılaştırmak, hangi parçada arama yapılacağını belirler.
k değerini bulmak için düşüş noktasında ikili arama yapın. Ortadaki değeri, aralığın son değeri olan nums[hi] ile karşılaştırın. nums[mid] > nums[hi] ise değerler mid sonrasında bir yerde düşer; bu nedenle en küçük değer onun sağındadır: lo = mid + 1 olarak ayarlayın. Aksi takdirde nums[mid..hi] düşüş olmadan yükselir; bu nedenle en küçük değer mid konumunda ya da onun öncesindedir: mid aralıkta kalacak şekilde hi = mid olarak ayarlayın. lo ile hi eşitlendiğinde, o indeks k olur.
target = 5 olan ilk örneği, [15, 19, 23, 2, 5, 8, 11], adım adım inceleyin. Ortadaki 2, 11'den büyük değildir; bu nedenle hi değeri 3 olur. Ardından 19, 2'den büyüktür; bu nedenle lo değeri 2 olur. Sonra 23, 2'den büyüktür; bu nedenle lo değeri 3 olur ve k = 3 elde edilir. 5, nums[3] = 2 ile nums[6] = 11 arasında olduğundan 3 ile 6 arasındaki indekslerde arama yapın; ikili arama 5 değerini 4. indekste bulur. İki ikili arama yaklaşık 2 log2 n adım sürer.
Algoritma
lo = 0vehi = n-1olarak ayarla.lo < hiolduğu sürecemiddeğerini hesapla;nums[mid] > nums[hi]iselo = mid + 1olarak ayarla, aksi takdirdehi = midolarak ayarla.- Son indekse
kadını ver: bu indeks en küçük değeri içerir. nums[k] ≤ target ≤ nums[n-1]isekilen-1arasındaki indekslerde ara; aksi takdirde 0 ilek-1arasındaki indekslerde ara.- Bu aralıkta standart ikili arama uygula ve
targetdeğerinin indeksini döndür; aralık boşalırsa-1dö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 -1Sıralı yarıda bir ikili arama
Sezgi
Dönme noktasının nerede olduğunu bilmen gerekmez. İkili aramanın olağan garantisini koru: target listede varsa, indeksi lo ile hi arasındadır. Ortadaki indekse, yani mid'e bak. Tüm listede değerler yalnızca bir kez düşer; dolayısıyla bu düşüş, mid'in çevresindeki iki yarıdan en fazla birindedir ve diğer yarı sıralıdır.
Sıralı yarıyı tek bir karşılaştırmayla bul. nums[lo] ≤ nums[mid] ise sol yarı nums[lo..mid]'de düşüş yoktur ve bu yarı sıralıdır. nums[mid]'in target olmadığını zaten bildiğin için, target bu yarıda ancak nums[lo] ≤ target < nums[mid] ise bulunabilir. Öyleyse hi = mid - 1 yap; değilse target yalnızca diğer yarıda olabilir, bu yüzden lo = mid + 1 yap. nums[lo] > nums[mid] olduğunda düşüş soldadır, sağ yarı nums[mid..hi] sıralıdır ve ayna koşulu olan nums[mid] < target ≤ nums[hi] kararı verir. Sıralı olmayan yarı hakkında doğrudan akıl yürütmezsin: target orada ancak sıralı yarıda olamayacağı kesinleştiğinde bulunur.
İlk örneği izleyelim: [15, 19, 23, 2, 5, 8, 11] ve target = 5. 0 ile 6 arasındaki aralığın ortası 3, değeri ise 2'dir. 15, 2'den büyük olduğundan sağ yarı [2, 5, 8, 11] sıralıdır ve 5 bu yarıda bulunur; bu nedenle lo 4 olur. 4 ile 6 arasındaki aralığın ortası 5, değeri ise 8'dir. Şimdi nums[4] = 5 ≤ 8; sol yarı [5, 8] sıralıdır ve 5'i içerir, bu nedenle hi 4 olur. 4. indekste 5 vardır: 4 döndür.
Düz ikili aramadaki gibi her adım aralığı yarıya indirir; bu nedenle döngü en fazla yaklaşık log2(n) + 1 kez çalışır: 5000 eleman için 13 adım ve ek bellek olarak iki indeks.
Algoritma
lo = 0vehi = n-1değerlerini ayarla.lo ≤ hiolduğu sürecemiddeğerini hesapla.nums[mid],target'a eşitsemiddeğerini döndür.nums[lo] ≤ nums[mid]ise sol yarı sıralıdır:nums[lo] ≤ target < nums[mid]isehi = mid - 1değerini ayarla, aksi hâldelo = mid + 1değerini ayarla.- Aksi hâlde sağ yarı sıralıdır:
nums[mid] < target ≤ nums[hi]iselo = mid + 1değerini ayarla, aksi hâldehi = mid - 1değerini ayarla. - Döngü sona erdiğinde
-1değ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
Tek geçişli arama kısadır ve hataların neredeyse tamamı karşılaştırma işleçlerinde bulunur.
nums[lo] < nums[mid]yerine≤yazmak. Geriye iki öğe kaldığındamid,lo'ya eşittir ve sol yarı, sıralı olan tek bir öğeden oluşur. Katı koşulla,[9, 4]vetarget = 4durumunda[9, 4]sıralı sağ yarı olarak kabul edilir; 4, 9 ile 4 arasındaki aralığın dışında bulunur ve-1döndürülür.- Düz ikili aramada olduğu gibi önce
targetilenums[mid]'i karşılaştırmak.[15, 19, 23, 2, 5, 8, 11]dizisindetarget = 19olduğunda, ortadaki 2 değeri 19'dan küçüktür; bu nedenle arama sağa ilerler ve 1. indeksi hiçbir zaman görmez. - Sıralı yarının yalnızca bir ucunu sınamak.
[40, 50, 60, 70, 80, 10, 20]dizisindetarget = 80olduğunda, ortadaki değer 70'tir ve sol yarı[40, 50, 60, 70]sıralıdır. Yalnızcatarget ≥ nums[lo]koşulunu denetlemek, 80 sayısı 40'tan büyük olduğu için aramayı sola yönlendirir; ancak 80, 70'ten de büyüktür ve bu nedenle sağ yarıda bulunur. Her iki ucu da denetleyin. - İki adımlı yaklaşımda döndürülmemiş durumu unutmak.
k = 0olduğunda ikinci aralık boştur ve aralığı0ile-1arasındadır. İşaretli indekslerle bu sorun olmaz; ancak işaretsiz indekslerle (Rust'ınusizetüründe)k - 1taşmaya neden olur. Rust kodunun yarı açık aralıklar kullanmasının nedeni budur. - Lua ve R'de konumun kendisini döndürmek. Bu dillerin listeleri 1'den başlar; bu nedenle döndürmeden önce 1 çıkarın.
Sıkça sorulan sorular4
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, tıpkı normal ikili aramada olduğu gibi mevcut aralığın bir yarısını tutar; bu nedenle 5000 elemanlı bir liste en fazla 13 adım gerektirir. Önce döndürme noktasını bulan iki aşamalı sürüm de yaklaşık iki kat fazla adımla O(log n) karmaşıklığındadır.
Bir döndürülmüş dizinin hangi yarısının sıralı olduğunu nasıl anlarsınız?
nums[lo] ile nums[mid] değerlerini karşılaştır. Değerler tüm listede yalnızca bir kez düşer. nums[lo] ≤ nums[mid] ise düşüş lo ile mid arasında değildir; dolayısıyla sol yarı sıralıdır. Aksi hâlde düşüş sol yarıdadır; bu da mid ile hi arasındaki sağ yarıda düşüş olmadığı ve bu yarının sıralı olduğu anlamına gelir.
Dizi yinelenen öğeler içerdiğinde algoritma çalışır mı?
Yazıldığı hâliyle değil. [1, 0, 1, 1, 1] içinde nums[lo], nums[mid] ve nums[hi] değerlerinin tümü 1 olduğundan, iki yarıdan hiçbirinin sıralı olduğu kanıtlanamaz. Genellikle uygulanan çözüm, nums[lo], nums[mid] ve nums[hi] eşit olduğunda lo değerini bir artırmaktır; bu, cevabı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ız, yoksa tek geçişte mi aramalısınız?
İkisi de O(log n) sürede çalışır. Minimumun indeksini bulmak, önce problemi iki basit ikili aramaya böler; böylece her parça, zaten güvendiğin kodu yeniden kullanır. Tek geçişli arama aynı işi daha az adımla tek bir döngüde yapar ve görüşmecilerin çoğunun beklediği sürüm budur.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def search(nums, target):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
nums = [15, 19, 23, 2, 5, 8, 11] target = 5
Beklenen
4