🎯 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)")

import bisect

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

# bisect_left: Elemanın eklenmesi gereken sol pozisyon
pos = bisect.bisect_left(dizi, 45)
print(f"\nbisect_left(45) = {pos}")

# Eleman var mı kontrol et
if pos < len(dizi) and dizi[pos] == 45:
    print(f"45 dizide var! İndeks: {pos}")
else:
    print("45 dizide yok")

# bisect_right: Elemanın eklenmesi gereken sağ pozisyon
# (Aynı elemanların sağına ekler)
print(f"\nbisect_right(45) = {bisect.bisect_right(dizi, 45)}")

# insort: Sıralı ekleme
print(f"\nOrijinal: {dizi}")
bisect.insort(dizi, 50)
print(f"50 eklendi: {dizi}")

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}")