İkili arama nasıl çalışır ve neyi gerektirir?

Question

Accepted Answer

**İkili arama**, **sıralanmış** bir dizide arama aralığını tekrar tekrar yarıya indirilmek suretiyle hedefi bulur. Her karşılaştırma, kalan öğelerin yarısını ortadan kaldırır ve **O(log n)** zaman verir. ## Fikir Ortadaki öğeye bakın. Hedefe eşitse bitti. Hedef daha küçükse, sol yarısı arayın; daha büyükse, sağ yarısı arayın. Bulunana veya aralık boşalana kadar tekrarlayın. ## Örnek ```python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 # middle index if arr[mid] == target: return mid # found it elif arr[mid] < target: lo = mid + 1 # discard left half else: hi = mid - 1 # discard right half return -1 # not present binary_search([1, 3, 5, 7, 9], 7) # -> 3 ``` ## İzleme ```text Search 7 in [1,3,5,7,9] lo=0 hi=4 mid=2 -> 5 < 7 => lo=3 lo=3 hi=4 mid=3 -> 7 == 7 => return 3 ``` ## Karmaşıklık - **Zaman:** O(log n). **Alan:** O(1) yinelemeli. ## Tuzaklar **Giriş sıralanmış olmalıdır** — aksi takdirde sonuçlar anlamsızdır. `lo`/`hi` içindeki kapalı-bir hataları ve bazı dillerde tamsayı taşması konusunda dikkat edin (`lo + (hi-lo)//2` kullanın). ## Neden önemli Arama alanını yarıya indirmek, bir milyonluk öğe aramasını ~20 karşılaştırmaya çevirir. Arkasındaki böl-ve-yönet deseni ağaçlarda, veritabanlarında ve sayısız mülakat probleminde yeniden ortaya çıkar. Tek zor gereksinimini bilmek — sıralanmış girdi — sizi klasik bir hassas hatadan korur.