Find First and Last Position of Element in Sorted Array
Azalan olmayan sırada sıralanmış bir tam sayı listesi nums ve bir tam sayı target veriliyor; dolayısıyla bir değer birden fazla kez bulunabilir. 0'dan başlayarak sayılan iki indeksin listesini döndür: target değerinin göründüğü ilk ve son konum. target listede yoksa [-1, -1] döndür. O(log n) zaman hedefle.
Fonksiyon
- numsinteger-array
- sıralanmış tam sayı listesi; değerler tekrarlanabilir
- targetinteger
- aranacak değer
- Döndürürinteger-array
- target'ın ilk ve son indeksi ya da bulunmuyorsa [-1, -1]
Kısıtlar
1 ≤ nums.length ≤ 104-104 ≤ nums[i], target ≤ 104numsazalmayan sırada sıralanmıştır.
Örnekler
- Girdi
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 5
- Çıktı
- [1, 3]
- Açıklama
- 5'in üç kopyası 1, 2 ve 3 indekslerinde yer alır; bu nedenle dizi 1'de başlar ve 3'te biter. 0 indeksinde 3, 4 indeksinde ise 8 bulunur; bu nedenle dizi daha ileri gidemez.
- Girdi
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 7
- Çıktı
- [-1, -1]
- Açıklama
- 7, 3. indeksteki 5 ile 4. indeksteki 8 arasında yer alır ve ikisi de 7 değildir. Listede 7'nin kopyası yoktur, bu nedenle yanıt
[-1, -1]olur.
Ek soru
Aynı liste, farklı hedefler için binlerce sorgu alıyorsa, önceden üzerinden bir kez geçmek her sorguyu O(log n)'den daha hızlı hâle getirebilir mi?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
numssıralı olduğu içintarget'ın tüm kopyaları tek bir grupta yan yana bulunur. Bu grubun iki ucunu bulman gerekir.Bir kopyayı bulup dışa doğru ilerlemek, tekrar dizisi uzunsa
O(n)maliyetine yol açabilir. Bunun yerine, eşleşme bulduktan sonra sola doğru devam edecek şekilde ikili aramayı değiştir: böylece aradığın sayıdan büyük veya ona eşit değere sahip ilk dizinde durur.nums[i] ≥ valuekoşulunu sağlayan ilk indeksi döndüren bir yardımcı işlev yazın. Dizinin başlangıcını bulmak için bunutargetile çağırın, oradaki değerintargetolduğunu kontrol edin vetarget + 1ile çağırın: dizi, bulunan indeksten bir önceki indekste sona erer.
Çözüm
Basit bir ikili arama, target değerinin karşılaştığı kopyasında durur ve bu kopya dizide herhangi bir yerde olabilir. Bunun yerine alt sınırı arayın: değeri verilen bir sayıya eşit veya ondan büyük olan ilk indeks. target ve target + 1 değerlerinin alt sınırları, O(log n) içinde dizinin her iki ucunu da verir.
Tüm listeyi tara
Sezgi
Listeyi bir kez dolaş. target değerini içeren ilk indeks başlangıç, son indeks ise bitiştir. target hiç görünmezse ikisi de -1 olarak kalır.
Bu yöntem sıralı olsun ya da olmasın her listede işe yarar; zayıf yanı da budur: n değerinin tümünü okur. 10^4 değerli bir liste, yaklaşık 28 karşılaştırmanın yeteceği yerde 10.000 karşılaştırmaya mal olur.
Algoritma
first = last = -1olarak ayarla.- Her
iindeksi için,nums[i]değeritarget'a eşitse,firsthâlâ-1isefirst = iolarak ayarla velast = iolarak ayarla. [first, last]değerini döndür.
def searchRange(nums, target):
first = last = -1
for i, value in enumerate(nums):
if value == target:
if first == -1:
first = i # the first match fixes the start
last = i # every later match moves the end
return [first, last]Bir kopyasını bul, ardından genişlet
Sezgi
target değerini içeren herhangi bir indeksi bulmak için ikili arama yapın. Liste sıralı olduğundan, her kopya bu indeksin çevresindeki kesintisiz bir aralıkta yer alır: Komşu hâlâ target olduğu sürece sola ve sağa ilerleyin.
Aramanın maliyeti O(log n), her kopya için bir adım ilerlemenin maliyeti ise toplamda k olur. Listenin çoğu target değerinden oluşuyorsa (örneğin 10^4 kopya), ilerleme her değeri okur ve yeniden doğrusal taramaya dönersiniz.
Algoritma
nums[found] == targetkoşulunu sağlayan herhangi birfoundindeksi için ikili arama yap.- Böyle bir indeks yoksa
[-1, -1]döndür. - Önündeki değer
targetdeğerine eşit olduğu sürecefirstdeğerinifoundkonumundan sola taşı. - Ardındaki değer
targetdeğerine eşit olduğu sürecelastdeğerinifoundkonumundan sağa taşı. [first, last]döndür.
def searchRange(nums, target):
# An ordinary binary search finds some copy of target, if there is one.
lo, hi = 0, len(nums) - 1
found = -1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
found = mid
break
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
if found == -1:
return [-1, -1]
# The copies sit next to each other, so walk out to both ends of the run.
first = last = found
while first > 0 and nums[first - 1] == target:
first -= 1
while last < len(nums) - 1 and nums[last + 1] == target:
last += 1
return [first, last]İki alt sınır ikili araması
Sezgi
Farklı bir soru sor: değeri en az value olan ilk indeks hangisi? Hiçbir değer koşulu karşılamıyorsa bu indeks alt sınırdır veya n olur. Her zaman bu indeksi içeren yarı açık bir [lo, hi) aralığını koru. nums[mid] < value ise mid ve öncesindeki her şey çok küçüktür. Aksi takdirde mid koşulu karşılar, ancak daha önceki bir indeks de karşılayabilir; bu nedenle yeni hi olarak mid aralıkta kalır. Eşleşme bulunduğunda döngü erken durmaz.
target değerinin alt sınırı, tekrar dizisinin başladığı yerdir. Değerler tam sayı olduğundan, target değerinden büyük ilk değer target + 1 değerinin alt sınırında bulunur ve tekrar dizisi bundan bir indeks önce biter. İlk örnekte 5'in alt sınırı 1, 6'nın alt sınırı ise 8'in bulunduğu 4'tür: tekrar dizisi [1, 3] olur. Tekrar dizisinin uzunluğu ne olursa olsun, iki arama 10^4 değer için yaklaşık 28 adım sürer.
Algoritma
lowerBound(value)fonksiyonunu yaz:lo = 0,hi = nile başla;lo < hiiken,nums[mid] < valueiselo = mid + 1yap, aksi hâldehi = midyap;lodeğerini döndür.first = lowerBound(target)olarak ayarla.first == nveyanums[first] != targetise[-1, -1]döndür.last = lowerBound(target + 1) - 1olarak ayarla ve[first, last]döndür.
def lowerBound(nums, value):
# The first index whose number is at least value, or len(nums) if none is.
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < value:
lo = mid + 1 # nums[mid] and everything before it is too small
else:
hi = mid # nums[mid] qualifies, but an earlier index might too
return lo
def searchRange(nums, target):
first = lowerBound(nums, target)
if first == len(nums) or nums[first] != target:
return [-1, -1]
# The run of target ends right before the first number above target.
last = lowerBound(nums, target + 1) - 1
return [first, last]
Tuzaklar ve uç durumlar
nums[mid] == targetolur olmaz dönmek. Bu indeks, eşit değerlerin bulunduğu aralığın herhangi bir yerinde olabilir:[3, 5, 5, 5, 8]dizisinde ilk orta indeks 2’dir; yani aralığın iki ucundan biri değildir.nums[mid] ≥ valueolduğunda alt sınır aramasındahi = mid - 1yazmak. Bu, cevap olabilecekmidindeksini aralıktan çıkarır.first < nolduğunu kontrol etmedennums[first]değerini okumak. Örneklerdeki 13 gibitargettüm değerlerden büyük olduğunda alt sınır, dizinin sonundan bir sonraki konum olannolur.- Lua ve R’deki kaydırmayı unutmak. Bu dillerde listeler 1’den başlar, bu yüzden her iki konumdan da 1 çıkarın.
Sıkça sorulan sorular3
İlk ve son konumu bulmanın zaman karmaşıklığı nedir?
O(log n) zaman ve O(1) alan, iki ikili aramayla. Hiçbiri eşleşme bulunca durmaz, bu nedenle maliyet hedef değerden kaç kopya bulunduğuna bağlı değildir: 10^4 değer için arama başına yaklaşık 14 adım.
İkili aramada alt sınır nedir?
Bir değerin alt sınırı, elemanı bu değere eşit veya ondan büyük olan ilk dizindir; böyle bir öğe yoksa listenin uzunluğudur. Listeyi sıralı tutmak için değerin ekleneceği yerdir. Üst sınır ise elemanı kesin olarak daha büyük olan ilk dizindir.
Tek bir ikili arama fonksiyonu hem ilk hem de son indeksi bulabilir mi?
Evet. Aramaya bir bayrak ekle: eşleşme bulunduğunda dizini kaydet ve ilk kopyayı bulmak için sola, sonuncuyu bulmak için sağa doğru aramaya devam et. target ve target + 1 üzerinde alt sınır araması yapmak da işe yarar. Her ikisi de O(log n) sürede çalışır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def searchRange(nums, target):
# Kodu buraya yazınTest #1
Test #2
Argümanlar
nums = [3, 5, 5, 5, 8, 9, 9, 12] target = 5
Beklenen Çıktı
[1, 3]