Döndürülmüş ve Sıralanmamış Dizilerde İkili Arama
Her adımda hangi yarının sıralı olduğuna karar vererek döndürülmüş sıralı dizide arama ve döndürülmüş dizide minimumu bulma problemlerini çözün.
Döndürülmüş ve Sıralanmamış Dizilerde İkili Arama, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 2. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Döndürülmüş Sıralı Dizi Nedir
Döndürülmüş sıralı dizi, bir dönme noktasından kesilip iki parçası yer değiştirilmiş sıralı bir dizidir. Örneğin [4, 5, 6, 7, 0, 1, 2], 4. dizininde döndürülmüş [0,1,2,4,5,6,7] sıralı dizisidir. Dizi artık bütünüyle sıralı olmadığından standart ikili arama burada başarısız olur.
Temel fikir şudur: herhangi bir döndürmeden sonra dizinin en az bir yarısı her zaman sıralıdır. Sınırları nereye taşıyacağınıza karar vermeden önce ikili aramanızın hangi yarının sıralı olduğunu belirlemesi gerekir.
# A rotated sorted array — one half is always sorted
arr = [4, 5, 6, 7, 0, 1, 2]
# Left half [4,5,6,7] is sorted
# Right half [0,1,2] is also sorted
# But left[0]=4 > right[-1]=2 => rotation happened in left-to-right crossingSıralı Yarının Belirlenmesi
mid hesaplandıktan sonra arr[lo] ile arr[mid] değerlerini karşılaştırın. Eğer arr[lo] <= arr[mid] ise, sol yarı sıralıdır; aksi hâlde sağ yarı sıralıdır. Hangi yarının sıralı olduğunu öğrendikten sonra hedefin bu sıralı aralıkta olup olmadığını kontrol edebilir ve aramayı buna göre daraltabilirsiniz.
Bu karar ağacı, her adımda dizinin tam yarısını elemenizi sağlar ve döndürülmüş bir dizide bile O(log n) karmaşıklığını korur.
def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
# Left half is sorted
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
# Right half is sorted
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0)) # 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3)) # -1Bir Örneği Adım Adım İzleme
search_rotated([4,5,6,7,0,1,2], 0) işlemini adım adım izleyelim. Başlangıçta lo=0, hi=6, mid=3, arr[mid]=7. Hedef 0, sıralı sol yarı olan [4..7] içinde mi? Hayır, bu nedenle lo=4 yaparız. Şimdi lo=4, hi=6, mid=5, arr[mid]=1. Sol yarı [0,1] sıralıdır (arr[lo]=0 <= arr[mid]=1). 0, [0..1) içinde mi? Evet, bu nedenle hi=4 yaparız. Şimdi lo=4, hi=4, mid=4, arr[4]=0 — 4 dizininde bulundu.
# Step-by-step trace
nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
steps = []
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
steps.append(f'lo={lo} hi={hi} mid={mid} val={nums[mid]}')
if nums[mid] == target:
steps.append(f'Found at {mid}')
break
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
for s in steps:
print(s)Döndürülmüş Dizide Yinelenen Değerleri Ele Alma
Döndürülmüş dizi yinelenen değerler içerebildiğinde (örneğin [1,3,1,1,1]), nums[lo] == nums[mid] koşulu belirsizdir — hangi yarının sıralı olduğunu anlayamazsınız. Güvenli çözüm, lo değerini artırmak (veya hi değerini azaltmak) ve yeniden denemektir. Bu, en kötü durumdaki süreyi O(n) düzeyine çıkarır; bunu mülakat sırasında belirtmelisiniz.
def search_rotated_with_dups(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return True
# Ambiguous: shrink left boundary
if nums[lo] == nums[mid] == nums[hi]:
lo += 1
hi -= 1
elif nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return False
print(search_rotated_with_dups([1, 3, 1, 1, 1], 3)) # True
print(search_rotated_with_dups([2, 2, 2, 0, 2], 0)) # TrueDöndürülmüş Sıralı Dizide En Küçük Değeri Bulma
Benzer bir problem, belirli bir hedefi aramak yerine döndürülmüş sıralı dizideki en küçük elemanı bulmayı ister. En küçük eleman her zaman sıralanmamış yarıdadır. Her adımda: arr[mid] > arr[hi] ise en küçük eleman sağ yarıdadır (lo = mid + 1); aksi hâlde mid dâhil sol yarıdadır (hi = mid). lo == hi olduğunda en küçük elemanı bulmuş olursunuz.
def find_min(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # min is in right half
else:
hi = mid # min is at mid or left of mid
return nums[lo]
print(find_min([3, 4, 5, 1, 2])) # 1
print(find_min([4, 5, 6, 7, 0, 1, 2])) # 0
print(find_min([11, 13, 15, 17])) # 11 (no rotation)arr[lo] <= arr[mid] Sıralı Sol Yarını Nasıl Belirler
arr[lo] <= arr[mid] koşulu, sıralı (veya döndürülmemiş) bir kesimde ilk elemanın her zaman en küçük olması nedeniyle işe yarar. arr[lo] <= arr[mid] ise [lo..mid] içinde döndürme gerçekleşmemiştir; dolayısıyla bu yarı sıralıdır. Eşitlik, lo == mid durumunu da ele alır; tek elemanlı bir kesim zaten sıralıdır.
Buna karşılık, arr[lo] > arr[mid] ise döndürme noktası lo ile mid arasında olmalıdır; bu da sağ yarının, yani [mid..hi] aralığının bitişik sıralı kesim olduğu anlamına gelir.
# Visualise: detect which half is sorted
examples = [
([4, 5, 6, 7, 0, 1, 2], 0, 6), # mid=3, val=7 => left sorted
([6, 7, 0, 1, 2, 4, 5], 0, 6), # mid=3, val=1 => right sorted
]
for arr, lo, hi in examples:
mid = lo + (hi - lo) // 2
if arr[lo] <= arr[mid]:
print(f'arr[{lo}]={arr[lo]} <= arr[{mid}]={arr[mid]} => LEFT half sorted')
else:
print(f'arr[{lo}]={arr[lo]} > arr[{mid}]={arr[mid]} => RIGHT half sorted')Karmaşıklık Analizi
Döndürülmüş sıralı bir dizide ikili aramayla arama yapmak, her yinelemede arama alanını ikiye böldüğümüz için O(log n) zaman ve O(1) bellek kullanmaya devam eder. Klasik ikili aramadan tek farkı, hangi yarının sıralı olduğunu belirlemek için ek bir sabit zamanlı kontrol yapılmasıdır.
Yinelenen değerler olduğunda, her adımda lo değerini yalnızca bir artırmamız gerekebileceği için en kötü durum O(n) düzeyine iner. Bu ödünleşimi açıkça belirtin — böylece sorunsuz senaryonun ötesindeki sınır durumlarını da düşündüğünüzü gösterirsiniz.
LeetCode 33 Uygulamalı İnceleme
LeetCode 33, “Döndürülmüş Sıralı Dizide Arama”, bu problemin temel biçimidir. Kısıtlar yinelenen değer olmadığını ve tam olarak bir döndürme yapıldığını garanti eder. Çözüm, daha önce yazdığımız search_rotated işlevidir. Mülakat açısından önemli noktalar: yinelenen değer olmadığı varsayımını her zaman belirtin, sınırdaki somut bir örnekle eşitsizliklerinizi doğrulayın ve hem bulunan hem de bulunamayan durumlarda döndürülen dizinin doğru olduğunu onaylayın.
# LeetCode 33 — complete solution
def search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]: # left half sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
# Tests
print(search([4,5,6,7,0,1,2], 0)) # 4
print(search([4,5,6,7,0,1,2], 3)) # -1
print(search([1], 0)) # -1LeetCode 153: Yinelenen Değer Olmadan En Küçük Değeri Bulma
LeetCode 153, “Döndürülmüş Sıralı Dizide En Küçük Değeri Bulma”, yinelenen değerler olmadan en küçük değeri bulmayı ister. Yaklaşım, en küçük değerin hangi tarafta olduğunu belirlemek için arr[mid] ile arr[hi] değerlerini (arr[lo] yerine) karşılaştırmaktır. arr[mid] > arr[hi] ise en küçük değer sağdadır; aksi hâlde mid konumunda veya solundadır. Bu yöntem, O(log n) içinde en küçük değere yakınsar.
def findMin(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
return nums[lo]
print(findMin([3,4,5,1,2])) # 1
print(findMin([4,5,6,7,0,1,2])) # 0
print(findMin([11,13,15,17])) # 11Döndürme Sayısı ve Pivot Dizini
En küçük elemanı bulabildiğinizde, döndürme sayısını da bilirsiniz: en küçük elemanın dizini, dizinin sağa kaç konum döndürüldüğünü tam olarak gösterir. Örneğin [4,5,6,7,0,1,2] dizisinde en küçük değer 4. dizindedir; dolayısıyla dizi 4 konum döndürülmüştür.
Pivotu bilmek, dizinleri n'e göre kalanları alınacak şekilde ele alarak standart ikili aramayı uygulamanızı sağlar: real_idx = (mid + pivot) % n. Bu alternatif biçim, döngüsel olarak dizinlenen yapılarla çalışırken akıl yürütmeyi kolaylaştırabilir.
def search_via_pivot(nums, target):
n = len(nums)
# Find pivot (index of minimum)
lo, hi = 0, n - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
pivot = lo
# Binary search with offset
lo, hi = 0, n - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
real_mid = (mid + pivot) % n
if nums[real_mid] == target:
return real_mid
elif nums[real_mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(search_via_pivot([4,5,6,7,0,1,2], 0)) # 4Hepsini Bir Araya Getirme
Bir mülakatta döndürülmüş dizi problemiyle karşılaştığınızda bu karar ağacını izleyin. Önce bir hedef bulmanız mı yoksa en küçük değeri bulmanız mı gerektiğini belirleyin. Hedef bulmak için sıralı yarıyı belirleme yaklaşımını kullanın. En küçük değeri bulmak için mid değerini hi ile karşılaştırın. Yinelenen değerler mümkünse en kötü durumun O(n) olduğunu belirtin ve sınırları daraltan geri dönüş çözümünü ekleyin.
Kodunuzu üç klasik örnek üzerinde izleyerek pratik yapın: döndürme yok, bir kez döndürülmüş ve en küçük değer son konuma gelecek şekilde döndürülmüş.
Hızlı Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını anlayıp anlamadığınızı test edin.
Ders Özeti
Bu derste şunları öğrendiniz: döndürülmüş sıralı bir dizinin her zaman en az bir sıralı yarısı vardır, nerede arama yapacağınıza karar vermeden önce hangi yarının sıralı olduğunu belirlemek için arr[lo] değerini arr[mid] ile karşılaştırmalısınız ve en küçük değeri bulmak, döndürme pivotunu belirlemek için arr[mid] ile arr[hi] değerlerini karşılaştırır. Sırada, alt sınır ve üst sınır ikili arama türlerini inceleyeceğiz.
Sıkça Sorulan Sorular
“Döndürülmüş ve Sıralanmamış Dizilerde İkili Arama” dersi ücretsiz mi?
Evet — “Döndürülmüş ve Sıralanmamış Dizilerde İkili Arama” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Döndürülmüş ve Sıralanmamış Dizilerde İkili Arama” dersinde ne öğreneceğim?
Her adımda hangi yarının sıralı olduğuna karar vererek döndürülmüş sıralı dizide arama ve döndürülmüş dizide minimumu bulma problemlerini çözün. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 2. dersidir.
“Döndürülmüş ve Sıralanmamış Dizilerde İkili Arama” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Klasik İkili Arama: Sol, Sağ, Orta
- Döndürülmüş ve Sıralanmamış Dizilerde İkili Arama
- Alt Sınır ve Üst Sınır
- Yanıt Uzayında İkili Arama