İçeriğe geç

İkili arama

Ders 2 / 8 · 5 dk

İkili arama

Adım 1/7

Dizi sıralı; bu yüzden ortadaki eleman, hedefin hangi yarıda olamayacağını söyler.

Fikir

Sıralı veride hedefi ortadaki elemanla karşılaştır ve hedefi içeremeyecek yarıyı at. Tek bir aday kalana kadar tekrarla. Bu yarıya bölme sana O(log n) kazandırır.

Gerçek hayattan örnek

Telefon rehberinde "Nadia" adını bulmak. Asla A'dan kaydırmaya başlamazsın; ortaya yakın bir yere atlarsın, M civarına düşersin ve ondan öncesini anında yok sayarsın. İki üç atlayış sonra oradasın.

Kod

Sıra sende

Boşluğu doldur.

nums = [1, 3, 5, 7, 9]
lo, hi = 0, 4
mid = (lo + hi) // 2
# nums[mid] is 5 and the target is 9 -> search right
lo = ___

Mini quiz

1 / 3

İkili arama (binary search), girdinin nasıl olmasını gerektirir?