🎯 6.2: İkili Arama (Binary Search)

def binary_search_iterative(arr, target):
    """
    İkili Arama - Iteratif Yöntem

    Args:
        arr: SIRALI dizi
        target: Aranan değer

    Returns:
        Bulunursa indeks, bulunamazsa -1
    """
    low = 0
    high = len(arr) - 1
    step = 0

    while low <= high:
        step += 1
        mid = (low + high) // 2

        print(f"Adım {step}: low={low}, high={high}, mid={mid}")
        print(f"         arr[{mid}] = {arr[mid]}")

        if arr[mid] == target:
            print(f"         ✅ BULUNDU!")
            return mid
        elif arr[mid] < target:
            print(f"         {arr[mid]} < {target} → Sağa git")
            low = mid + 1
        else:
            print(f"         {arr[mid]} > {target} → Sola git")
            high = mid - 1

    print("❌ Bulunamadı!")
    return -1

# Test
dizi = [11, 12, 22, 25, 34, 45, 64, 78, 90]
print(f"Sıralı Dizi: {dizi}")
print(f"Aranan: 45\n")

sonuc = binary_search_iterative(dizi, 45)
print(f"\nSonuç: İndeks = {sonuc}")

def binary_search_recursive(arr, target, low, high, step=1):
    """
    İkili Arama - Recursive Yöntem
    """
    if low > high:
        return -1

    mid = (low + high) // 2
    print(f"Adım {step}: arr[{mid}] = {arr[mid]} {'✅' if arr[mid] == target else ''}")

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high, step + 1)
    else:
        return binary_search_recursive(arr, target, low, mid - 1, step + 1)

# Test
dizi = [11, 12, 22, 25, 34, 45, 64, 78, 90]
print(f"Sıralı Dizi: {dizi}")
print(f"Aranan: 22\n")

sonuc = binary_search_recursive(dizi, 22, 0, len(dizi) - 1)
print(f"\nSonuç: İndeks = {sonuc}")

print("\n" + "="*40)
print("Recursive vs Iterative:")
print("- Recursive: Daha okunaklı, ama call stack kullanır")
print("- Iterative: Daha verimli (O(1) ek alan)")

# ==========================================
# PYTHON BISECT MODÜLÜ - HAZIR BINARY SEARCH
# ==========================================

import bisect

dizi = [11, 12, 22, 25, 34, 45, 64, 78, 90]
print(f"📋 Sıralı Dizi: {dizi}")
print("=" * 50)

# --------- bisect_left ---------
# x değerinin eklenmesi gereken EN SOL pozisyonu bulur
# Eğer x zaten varsa, mevcut x'lerin SOLUNA ekler
print("\n🔍 bisect_left örnekleri:")

pos = bisect.bisect_left(dizi, 45)
print(f"  bisect_left(45) = {pos}")
print(f"  → 45 dizide {'VAR' if pos < len(dizi) and dizi[pos] == 45 else 'YOK'}!")

# Olmayan bir değer için
pos2 = bisect.bisect_left(dizi, 30)
print(f"  bisect_left(30) = {pos2}")
print(f"  → 30 olsaydı indeks {pos2}'e eklenmeli (25 ile 34 arasına)")

# --------- bisect_right ---------
# x değerinin eklenmesi gereken EN SAĞ pozisyonu bulur
print("\n🔍 bisect_right örneği:")
tekrarli = [1, 2, 3, 3, 3, 3, 4, 5]
print(f"  Dizi: {tekrarli}")
print(f"  bisect_left(3)  = {bisect.bisect_left(tekrarli, 3)} (ilk 3'ün soluna)")
print(f"  bisect_right(3) = {bisect.bisect_right(tekrarli, 3)} (son 3'ün sağına)")

# --------- insort ---------
# Elemanı sıralı şekilde ekler (bul + ekle tek adımda)
print("\n🔍 insort örneği:")
print(f"  Orijinal: {dizi}")
bisect.insort(dizi, 50)
print(f"  50 eklendi: {dizi}")
print(f"  → 50, sırayı bozmadan doğru yere yerleşti!")

def find_first(arr, target):
    """Target'ın İLK göründüğü indeksi bulur"""
    low, high = 0, len(arr) - 1
    result = -1

    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
        else:
            high = mid - 1

    return result

def find_last(arr, target):
    """Target'ın SON göründüğü indeksi bulur"""
    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

# Test
dizi = [1, 2, 3, 3, 3, 3, 4, 5, 6]
print(f"Dizi: {dizi}")
print(f"Aranan: 3")

ilk = find_first(dizi, 3)
son = find_last(dizi, 3)

print(f"\nİlk 3'ün indeksi: {ilk}")
print(f"Son 3'ün indeksi: {son}")
print(f"3'ün sayısı: {son - ilk + 1}")