Pratik Yaparak Öğrenin
Bu sayfada arama algoritmaları ile ilgili klasik mülakat sorularını ve algoritma problemlerini çözeceğiz. Her problem için:
Binary Search algoritmasını kendi değerlerinizle test edin!
Sıralı bir dizide, hedef değerin ilk ve son göründüğü indeksleri bulan bir fonksiyon yazın. Eleman yoksa [-1, -1] döndürün.
Problem: Normal binary search elemanı bulduğunda hemen durur. Ama ya aynı elemandan birden fazla varsa? Hangisini bulduğumuzu bilemeyiz!
[1, 2, 3, 3, 3, 3, 4, 5], hedef = 3
Normal binary search mid = 3 veya 4'te durabilir. Ama biz ilk 3 (indeks 2) ve son 3 (indeks 5) istiyoruz!
high = mid - 1 yaplow = mid + 1 yapZaman: İki ayrı binary search: O(log n) + O(log n) = O(log n) (sabitler Big-O'da düşer)
# ===========================================
# İLK VE SON EŞLEŞMEYİ BULMA - Binary Search
# ===========================================
def find_first(arr, target):
"""
Hedef değerin İLK göründüğü indeksi bulur.
Fark: Eleman bulununca durmuyoruz,
sola bakmaya DEVAM ediyoruz (daha erken indeks var mı?)
"""
low, high = 0, len(arr) - 1
result = -1 # Sonucu sakla
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
result = mid # Bulduk! Ama daha solda olabilir
high = mid - 1 # Sola bakmaya devam
elif arr[mid] < target:
low = mid + 1 # Sağa git
else:
high = mid - 1 # Sola git
return result
def find_last(arr, target):
"""
Hedef değerin SON göründüğü indeksi bulur.
Fark: Eleman bulununca durmuyoruz,
sağa bakmaya DEVAM ediyoruz (daha geç indeks var mı?)
"""
low, high = 0, len(arr) - 1
result = -1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
result = mid # Bulduk! Ama daha sağda olabilir
low = mid + 1 # Sağa bakmaya devam
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return result
def search_range(arr, target):
"""İlk ve son indeksi birlikte döndür"""
return [find_first(arr, target), find_last(arr, target)]
# ============ TEST ============
print("=" * 50)
dizi = [1, 2, 3, 3, 3, 3, 4, 5]
hedef = 3
print(f"Dizi: {dizi}")
print(f"Hedef: {hedef}")
print()
ilk = find_first(dizi, hedef)
son = find_last(dizi, hedef)
print(f"İlk görünme indeksi: {ilk}")
print(f"Son görünme indeksi: {son}")
print(f"Toplam {hedef} sayısı: {son - ilk + 1} adet")
print()
print(f"search_range sonucu: {search_range(dizi, hedef)}")
print("\n" + "=" * 50)
print("Olmayan eleman testi:")
print(f"search_range([1,2,4,5], 3) = {search_range([1,2,4,5], 3)}")Sıralı bir dizi bilinmeyen bir pivot noktasından döndürülmüş. Bu dizide hedef elemanı O(log n) zamanda bulun.
🔄 Döndürme (Rotation) Ne Demek?
Sıralı bir diziyi al, bir noktadan kes ve iki parçayı yer değiştir:
Sağ taraf sola geçti, sol taraf sağa geçti. Ama her iki parça kendi içinde hâlâ sıralı!
🔑 Kritik Gözlem: Neden Her Zaman Bir Yarı Sıralı?
Dizimiz: [4, 5, 6, 7, 0, 1, 2]
📐 Hangi Yarının Sıralı Olduğunu Nasıl Anlarız?
Sol yarı sıralıdır! (Çünkü başlangıç ≤ orta, artış var)
Örnek: [4,5,6,7] → 4 ≤ 7 ✓
Sağ yarı sıralıdır! (Sol yarıda kırılma var)
Örnek: [6,7,0,1,2] için mid=0 → 6 > 0
🎯 Strateji:
arr[low] ≤ arr[mid] ise sol yarı sıralıdır. Aksi halde sağ yarı sıralıdır.
# ================================================
# DÖNDÜRÜLMÜŞ DİZİDE BINARY SEARCH
# ================================================
def search_rotated(arr, target):
"""
Döndürülmüş sıralı dizide arama.
Anahtar fikir: Her zaman bir yarı tamamen sıralıdır!
Bu sıralı yarıyı kullanarak karar veririz.
"""
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
# Bulduk!
if arr[mid] == target:
return mid
# Sol yarı sıralı mı kontrol et
if arr[low] <= arr[mid]:
# Sol yarı sıralı [low...mid]
# Target bu aralıkta mı?
if arr[low] <= target < arr[mid]:
high = mid - 1 # Sola git
else:
low = mid + 1 # Sağa git
else:
# Sağ yarı sıralı [mid...high]
# Target bu aralıkta mı?
if arr[mid] < target <= arr[high]:
low = mid + 1 # Sağa git
else:
high = mid - 1 # Sola git
return -1 # Bulunamadı
# ============ TEST ============
print("=" * 50)
print("DÖNDÜRÜLMÜŞ DİZİDE ARAMA")
print("=" * 50)
dizi = [4, 5, 6, 7, 0, 1, 2]
print(f"\nDizi: {dizi}")
print("(Orijinal [0,1,2,4,5,6,7] 4'ten döndürülmüş)")
test_values = [0, 4, 7, 2, 3]
for target in test_values:
result = search_rotated(dizi, target)
status = f"indeks {result}" if result != -1 else "bulunamadı"
print(f" Ara({target}) → {status}")
print("\n" + "=" * 50)
print("Farklı döndürme örneği:")
dizi2 = [6, 7, 0, 1, 2, 4, 5]
print(f"Dizi: {dizi2}")
print(f" Ara(0) → indeks {search_rotated(dizi2, 0)}")
print(f" Ara(5) → indeks {search_rotated(dizi2, 5)}")Negatif olmayan bir tamsayının karekökünü bulun. Sonuç tamsayı olmalı (aşağı yuvarla).
🤔 Neden Binary Search Kullanabiliriz?
Binary search için bir sıralı yapı lazım. Kareler sıralı mı?
✓ Evet! Sayılar arttıkça kareleri de artar. Bu sıralı bir dizi gibi düşünülebilir!
📐 Problem Nasıl Dönüşüyor?
Orijinal soru: √16 = ?
Dönüştürülmüş soru: mid² = 16 olan mid'i bul!
Yani [1, 2, 3, 4, 5, ...] dizisinde mid² == 16 olan mid'i arıyoruz.
🎯 Arama Mantığı:
mid, cevap olabilir! Kaydet ve daha büyük dene (low = mid + 1)
mid çok büyük, daha küçük dene (high = mid - 1)
📝 Örnek: √8 = ?
mid'i bulmak istiyoruz, bu yüzden mid² ≤ n ise kaydet VE aramaya devam et.
# ====================================
# BINARY SEARCH İLE KAREKOK BULMA
# ====================================
def sqrt_binary_search(n):
"""
n'in tamsayı karekökünü bul.
Arama aralığı: [0, n]
Hedef: mid² ≤ n olan en büyük mid
"""
if n < 2:
return n # 0 veya 1
low, high = 1, n // 2 # √n en fazla n/2 olabilir (n ≥ 2 için)
result = 1
while low <= high:
mid = (low + high) // 2
square = mid * mid
print(f" low={low}, high={high}, mid={mid}, mid²={square}")
if square == n:
return mid # Tam karekök!
elif square < n:
result = mid # Kaydet, daha büyük olabilir
low = mid + 1
else:
high = mid - 1
return result
# ============ TEST ============
print("=" * 50)
print("BINARY SEARCH İLE KAREKOK")
print("=" * 50)
test_cases = [16, 8, 25, 26, 100, 2]
for n in test_cases:
print(f"\n√{n} hesaplanıyor:")
result = sqrt_binary_search(n)
print(f" Sonuç: {result} (kontrol: {result}² = {result**2})")
print("\n" + "=" * 50)
print("Büyük sayı testi:")
print(f"√1000000 = {sqrt_binary_search(1000000)}")Bir dizide "tepe elemanı" (peak element), komşularından büyük olan elemandır. Herhangi bir tepe elemanının indeksini bulun.
⛰️ Tepe Elemanı Ne Demek?
Bir eleman, sağ ve sol komşularından büyükse "tepe"dir. Dağın zirvesi gibi düşün!
Not: Dizinin uçlarında sadece bir komşu var. Uçtaki eleman tek komşusundan büyükse tepe sayılır.
🔑 Binary Search Neden Çalışıyor?
Dizi sıralı değil! Ama binary search yine de çalışıyor. Nasıl?
Garanti: Eğer yukarı çıkıyorsak (arr[mid] < arr[mid+1]), o yönde mutlaka bir tepe var!
📐 Karar Mantığı:
Yokuş yukarı gidiyoruz! Tepe sağda → low = mid + 1
Yokuş aşağı veya zirvedeyiz! mid tepe olabilir → high = mid
📝 Örnek: [1, 2, 1, 3, 5, 6, 4]
low < high kullanıyoruz? low ≤ high değil? Çünkü tek eleman kaldığında (low == high) o elemanın tepe olduğunu biliyoruz!
# ====================================
# PEAK ELEMENT BULMA
# ====================================
def find_peak_element(arr):
"""
Tepe elemanının indeksini bul.
Tepe = Komşularından büyük olan eleman
Binary search ile O(log n) çözüm
"""
low, high = 0, len(arr) - 1
while low < high:
mid = (low + high) // 2
print(f" low={low}, high={high}, mid={mid}, arr[mid]={arr[mid]}")
# Sağ komşuyla karşılaştır
if arr[mid] < arr[mid + 1]:
# Yükseliyor, tepe sağda
low = mid + 1
print(f" {arr[mid]} < {arr[mid+1]}, sağa git")
else:
# Düşüyor veya mid tepe, sol tarafa bak
high = mid
print(f" {arr[mid]} >= {arr[mid+1]}, sola git (veya mid tepe)")
# low == high olduğunda, bu tepe noktası
return low
# ============ TEST ============
print("=" * 50)
print("PEAK ELEMENT BULMA")
print("=" * 50)
test_cases = [
[1, 2, 3, 1], # Tek tepe: indeks 2
[1, 2, 1, 3, 5, 6, 4], # Birden fazla tepe
[1, 2, 3, 4, 5], # Artan dizi, tepe sonda
[5, 4, 3, 2, 1], # Azalan dizi, tepe başta
]
for arr in test_cases:
print(f"\nDizi: {arr}")
peak_idx = find_peak_element(arr)
print(f"Tepe indeks: {peak_idx}, Değer: {arr[peak_idx]}")
# Doğrulama
left_ok = peak_idx == 0 or arr[peak_idx] > arr[peak_idx-1]
right_ok = peak_idx == len(arr)-1 or arr[peak_idx] > arr[peak_idx+1]
status = "✅ Geçerli tepe" if left_ok and right_ok else "❌ Hata!"
print(f" {status}")Sıralı bir dizide, hedef elemanın kaç kez göründüğünü bulun.
🤔 Neden Linear Search Yetersiz?
Tüm diziyi tarayıp sayabiliriz (O(n)), ama sıralı dizide binary search ile O(log n) yapabiliriz!
💡 Ana Fikir: Soru 1'i Kullan!
Dizi sıralı olduğu için aynı elemanlar ardışık duruyor:
Sayı = Son İndeks - İlk İndeks + 1 = 5 - 2 + 1 = 4
📋 Adımlar:
find_first(arr, target) ile ilk görünme indeksini bulfind_last(arr, target) ile son görünme indeksini bulcount = last - first + 1📝 Örnek Detay:
# ====================================
# SIRALI DİZİDE ELEMAN SAYMA
# ====================================
def find_first(arr, target):
"""Hedefin ilk görünme indeksi"""
low, high = 0, len(arr) - 1
result = -1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
result = mid
high = mid - 1 # Sola devam
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return result
def find_last(arr, target):
"""Hedefin son görünme indeksi"""
low, high = 0, len(arr) - 1
result = -1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
result = mid
low = mid + 1 # Sağa devam
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return result
def count_occurrences(arr, target):
"""
Hedef elemanın kaç kez göründüğünü bul.
O(log n) - İki binary search
"""
first = find_first(arr, target)
# Eleman yoksa 0 döndür
if first == -1:
return 0
last = find_last(arr, target)
# Sayı = son_indeks - ilk_indeks + 1
return last - first + 1
# ============ TEST ============
print("=" * 50)
print("SIRALI DİZİDE ELEMAN SAYMA")
print("=" * 50)
dizi = [1, 1, 2, 2, 2, 2, 3]
print(f"\nDizi: {dizi}")
for target in [1, 2, 3, 4]:
count = count_occurrences(dizi, target)
print(f" {target} sayısı: {count} kez")
print("\n" + "=" * 50)
print("Büyük örnek:")
import random
big_arr = sorted([random.randint(1, 10) for _ in range(100)])
print(f"100 elemanlı rastgele dizi (1-10 arası)")
for i in range(1, 11):
print(f" {i}: {count_occurrences(big_arr, i)} kez")Sıralı bir dizide, toplamı hedef değere eşit olan iki sayının indekslerini bulun.
🎯 Problem Analizi
Aradığımız: arr[i] + arr[j] = target olan i, j çifti
Örnek: [2, 7, 11, 15], hedef=9 → 2 + 7 = 9 ✓
📊 3 Farklı Yaklaşım:
Her çifti dene: (0,1), (0,2), (0,3), (1,2)... Çok yavaş!
Her arr[i] için, (target - arr[i]) değerini binary search ile ara.
Dizi sıralı olduğu için iki işaretçi kullanabiliriz.
🔑 Two Pointer Nasıl Çalışır?
left = 0 (en küçük), right = n-1 (en büyük)
left++right--📝 Örnek Simülasyon: [2, 7, 11, 15], hedef=9
❓ Neden Two Pointer Çalışıyor?
Dizi sıralı! right-- dersek toplam azalır, left++ dersek toplam artar. Bu sayede hedefe doğru sistematik olarak yaklaşırız.
# ====================================
# TWO SUM - SIRALI DİZİ
# ====================================
# YÖNTEM 1: Binary Search
def two_sum_binary(arr, target):
"""
Her eleman için tamamlayıcıyı binary search ile ara.
O(n log n)
"""
def binary_search(arr, target, left):
low, high = left + 1, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
for i in range(len(arr) - 1):
complement = target - arr[i] # Ne lazım?
j = binary_search(arr, complement, i)
if j != -1:
return [i, j]
return [-1, -1]
# YÖNTEM 2: Two Pointer (En İyi!)
def two_sum_two_pointer(arr, target):
"""
Sıralı dizi avantajı: Two pointer tekniği!
O(n)
"""
left, right = 0, len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1 # Daha büyük sayı lazım
else:
right -= 1 # Daha küçük sayı lazım
return [-1, -1]
# ============ TEST ============
print("=" * 50)
print("TWO SUM - SIRALI DİZİ")
print("=" * 50)
dizi = [2, 7, 11, 15]
target = 9
print(f"\nDizi: {dizi}")
print(f"Hedef toplam: {target}")
result_binary = two_sum_binary(dizi, target)
result_two_ptr = two_sum_two_pointer(dizi, target)
print(f"\nBinary Search sonucu: {result_binary}")
print(f"Two Pointer sonucu: {result_two_ptr}")
# Doğrulama
i, j = result_two_ptr
if i != -1:
print(f"Kontrol: {dizi[i]} + {dizi[j]} = {dizi[i] + dizi[j]} ✅")
print("\n" + "=" * 50)
print("Olmayan toplam testi:")
print(f"two_sum([1,2,3], 10) = {two_sum_two_pointer([1,2,3], 10)}")