Taban durum
- Algoritmalar kursu
- Başlangıç
- Ders 55/80
- 4 dk
low > high olduğunda eleman yok sayıldığını öğrenirsin.
Taban durum
İkili aramanın taban durumu left > right'tır. Bu, arama aralığının boş olduğu ve hedefin bulunamadığı anlamına gelir.
Bu durumda -1 döndürülür. While döngüsü left <= right koşuluyla döndüğü için bu durum doğal olarak sonlanır.
Recursive ikili arama
İkili arama recursive olarak da yazılabilir: search(arr, target, left, right). Taban durum left > right ise -1.
Recursive versiyon daha zarif olabilir ama yığın alanı kullanır. İteratif versiyon O(1) bellek ile daha verimlidir.
Uygulama Recursive ikili arama
binary_rec(arr, target, left, right) yaz. Recursive olarak ara. print(binary_rec([2, 4, 6, 8], 6, 0, 3)) ile 2 yazdır.
Başlangıç kodu
def binary_rec(arr, target, left, right):
# Recursive araÖrnek çözüm
def binary_rec(arr, target, left, right):
# Recursive ara
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_rec(arr, target, mid + 1, right)
else:
return binary_rec(arr, target, left, mid - 1)
print(binary_rec([2, 4, 6, 8], 6, 0, 3))Beklenen çıktı
2
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Taban durum: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
left > right |
Taban |
return -1 |
Bulunamadı |
while |
İteratif |
Recursive |
Yığın kullanır |
2 İkili arama ne zaman -1 döndürür?
- Hedef bulunduğunda
- left > right olduğunda Doğru cevap
- Dizi boş olduğunda
- mid = 0 olduğunda
Açıklama: left > right olduğunda -1 döndürülür.
3 Döngü koşulu
while ____: ile döngü döner.while left <= right: ile döngü döner.Açıklama: left <= right doğru.